透过链表看递归 - 超级大汇总——DBC的博客超级大汇总—

一、我们先来看力扣的第203题

203. 移除链表元素

具体题目

第一种：不使用虚拟头结点

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
//                ListNode delNode = prev.next;
//                prev.next = delNode.next;
//                delNode.next = null;
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }
}

第二种：使用虚拟头结点

public class Solution2 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

温馨提示

两种均可以实现对应需求，第二种不需要进行判断，简化了一些流程

力扣提交情况——第二种提交

二、不用力扣测试，自己编写代码测试一下我们自己的链表

ListNode

点击查看完整内容

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    //  链表节点的构造函数
    //  使用arr为参数，创建一个链表，当前的ListNode为链表头结点
    ListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    //  以当前节点为头结点的链表信息字符串
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            res.append(cur.val + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}

main方法测试一下

    public static void main(String[] args) {
        int[] nums = {1,2,3,5,6,7,8,5,6};
        ListNode head = new ListNode(nums);
        System.out.println(head);

        ListNode res = new Solution2().removeElements(head,6);
        System.out.println(res);
    }

输出结果

三、我们再来看一种递归的解决方案

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

运行情况和提交力扣情况

温馨提示

依然可以实现，真是神鬼莫测，哈哈哈！给我学！！！ [aru_56]
代码量更加少了，更加的简洁，而且，我们甚至没有看到删除的操作，但是确实已经删除了！

四、递归函数的“微观”解读

我们来看一个简单的例子来更好的理解递归思想

我们需要使用递归的方式来统计一下这个数组值的和
arr = [6，10]

我们来看一看这个代码，这就是一种递归的思想

    public static int sum(int[] arr, int l) {
        if (l == arr.length) {
            return 0;
        }
        int x = sum(arr, l + 1);
        int res = arr[l] + x;
        return res;
    }

这里我们用一张图来展示，引用全网最屌算法教程（个人认为）慕课网算法名师Liuyubobobo的图片来更好的说明这个例子

解析

我们统称上面的方法叫做方法A，我们递归的思想就是方法A调用方法A，层层调用，我们可以看到，在满足最后一个条件的时候，方法进行了return，然后再层层return回来，这个就是简单的递归思想了！

我们来看一个叫复杂的例子来更好的理解递归思想

温馨提示

与上面的原理一样，相信很好理解，如果head.val = val 那么我们就直接返回下一个（head.next），那么就相当于删掉了一个，是不是很有意思！哈哈哈[aru_56]

总结

递归调用是有代价的：函数调用+系统栈控件
程序调用的系统栈

五、递归算法的调试

点击查看完整内容

    public ListNode removeElements(ListNode head, int val, int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println("Call: remove " + val + " in " + head);
        if (head == null) {
            System.out.print(depthString);
            System.out.print("Return: " + head);
            return head;
        }
        ListNode res = removeElements(head.next, val, depth + 1);
        System.out.print(depthString);
        System.out.println("After remove " + val + ": " + res);
        ListNode ret;
        if (head.val == val) {
            ret = res;
        } else {
            head.next = res;
            ret = head;
        }
        System.out.print(depthString);
        System.out.println("Return: " + ret);
        return ret;
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }

控制台输出

点击查看完整内容

1->2->3->5->6->7->8->5->6->NULL
Call: remove 6 in 1->2->3->5->6->7->8->5->6->NULL
--Call: remove 6 in 2->3->5->6->7->8->5->6->NULL
----Call: remove 6 in 3->5->6->7->8->5->6->NULL
------Call: remove 6 in 5->6->7->8->5->6->NULL
--------Call: remove 6 in 6->7->8->5->6->NULL
----------Call: remove 6 in 7->8->5->6->NULL
------------Call: remove 6 in 8->5->6->NULL
--------------Call: remove 6 in 5->6->NULL
----------------Call: remove 6 in 6->NULL
------------------Call: remove 6 in null
------------------Return: null----------------After remove 6: null
----------------Return: null
--------------After remove 6: null
--------------Return: 5->NULL
------------After remove 6: 5->NULL
------------Return: 8->5->NULL
----------After remove 6: 8->5->NULL
----------Return: 7->8->5->NULL
--------After remove 6: 7->8->5->NULL
--------Return: 7->8->5->NULL
------After remove 6: 7->8->5->NULL
------Return: 5->7->8->5->NULL
----After remove 6: 5->7->8->5->NULL
----Return: 3->5->7->8->5->NULL
--After remove 6: 3->5->7->8->5->NULL
--Return: 2->3->5->7->8->5->NULL
After remove 6: 2->3->5->7->8->5->NULL
Return: 1->2->3->5->7->8->5->NULL
1->2->3->5->7->8->5->NULL

温馨提示

我们也可以通过这种控制台输出的方式来看我们的递归算法相关

六、链表中最经典的问题，翻转列表

力扣第206题——翻转链表

点我前往

题目速览

我们可以定义三个变量来帮助我们实现，如下面这种方式

温馨提示

三个变量依次向右推，直到cur == null为止，这样pre就是最后一个了，我们就实现了我们想要的效果！

具体代码如下

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur !=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }
}

力扣执行结果

七、翻转列表的递归实现

我们先看这串代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode rev = reverseList(head.next);
    }
}

我们从宏观概念上，我们会得到如下链表

温馨提示

也就是 5 -> 4 -> 3 -> 2 -> null
至于这里为什么2指向的是null而不是head，我相信很简单，如果不理解，可以自己慢慢调试一下。
这里我们当然没有实现，因为我们想要的是2指向1，而1又要指向null，这样才是我们想要的结果。
这里我们也可以清晰的看到，1是head，那么就简单啦，我们直接head.next.next = head ，这样，我们就把2指向了1了，但是这个时候1还是指向着2，所以我们还需要 head.next = null ,这样即可实现我们想要的操作了！

完整代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode rev = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return rev;
    }
}