透过链表看递归

DBC 1.5K 0

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

203. 移除链表元素

[aru_47] 点我前往

具体题目

透过链表看递归插图

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

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;
    }
}
温馨提示

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

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

透过链表看递归插图2

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

ListNode

点击查看完整内容

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);
    }

输出结果

透过链表看递归插图4

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

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;
    }
}

运行情况和提交力扣情况

透过链表看递归插图6
透过链表看递归插图8

温馨提示

依然可以实现,真是神鬼莫测,哈哈哈!给我学!!! [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的图片来更好的说明这个例子

透过链表看递归插图10

解析

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

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

透过链表看递归插图12

温馨提示

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

总结

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

五、递归算法的调试

点击查看完整内容

控制台输出

点击查看完整内容
温馨提示

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

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

力扣第206题——翻转链表

点我前往

题目速览

透过链表看递归插图14

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

透过链表看递归插图16

温馨提示

三个变量依次向右推,直到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;

    }
}

力扣执行结果

透过链表看递归插图18

七、翻转列表的递归实现

我们先看这串代码

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

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

透过链表看递归插图20

温馨提示

也就是 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;
    }
}

至于为什么输出的是rev,我相信很简单啦,因为我们翻转链表,根据我们的需要,它就是第一个了,从上面的图中也可以清晰的看出来!

力扣输出

透过链表看递归插图22

发表评论 取消回复
表情 图片 链接 代码

分享