5-玩转数据结构-链表与递归

2018-08-12 本文已影响25人天涯明月笙

前面我们实现了一个单链表，用它又实现了栈和队列，实现队列时对于链表进行了改进。链表与递归，递归和树联系在一起。但链表天然和递归有关，链表的递归学习会对后面我们理解树相关递归有帮助。

LeetCode问题，不以我们自己的链表类实现为基础，它上面的很多以节点为中心。

https://leetcode-cn.com/problems/remove-linked-list-elements/description/

删除链表中的节点

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

注意: 两个6都要删除。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public ListNode removeElements(ListNode head, int val) {
    }
}

可以看到LeetCode给我们的Solution模板中有注释代码，有一个已经定义好的ListNode类，只是告诉我们底下Solution中的方法可以使用这个对象，对象里存储了怎样的成员变量。listNode不能被提交。

我们新建工程: 创建Solution类，将LeetCode的模板粘贴进来，我们没有ListNode类，因此要新建一个ListNode类。

package cn.mtianyan;

public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
}

想要删除一个元素，要找到这个节点之前的那个节点才方便删除。对于头结点要特殊处理，或使用虚拟头结点。

        if (head != null && head.val == val){
            
        }

这句话是对于头结点做单独处理，但是前提条件是head非空。

        if (head != null && head.val == val){
            ListNode delNode = head;    // 保存head对象
            head = head.next;           // head后移
            delNode.next = null;        // head脱离链表
        }

通过上面的代码我们可以成功的删除头结点，但是有可能新的头结点还是等于val。因此应该变为while循环。

        while (head != null && head.val == val){
            ListNode delNode = head;    // 保存head对象
            head = head.next;           // head后移
            delNode.next = null;        // head脱离链表
        }

这样就把开头的都删除了。

        if (head == null)
            return null;

这里要考虑到链表中全部元素都是val，上面的while就删除完了。

while (prev.next != null){
            if (prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next; // prev.next.next
                delNode.next = null;
                // 这里prev不需要后挪，因为删除之后，prev.next节点已经变了，有可能还是val要删除。
            }else {
                prev = prev.next;
            }
        }

在LeetCode上提交代码我们不需要考虑内存泄漏等问题，它运行完一定会被回收，因此代码可以简化。

class Solution {

    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val){
            // ListNode delNode = head;    // 保存head对象
            head = head.next;           // head后移
            // delNode.next = null;        // head脱离链表
        }
        if (head == null)
            return null;
        ListNode prev =head;
        while (prev.next != null){
            if (prev.next.val == val){
                // ListNode delNode = prev.next;
                prev.next = prev.next.next; // prev.next.next
                // delNode.next = null;
                // 这里prev不需要后挪，因为删除之后，prev.next节点已经变了，有可能还是val要删除。
            }else {
                prev = prev.next;
            }
        }
        return head;
    }
}

使用虚拟头结点实现方式。

package cn.mtianyan;

class SolutionDummyHead {

    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){
                ListNode delNode = prev.next;
                prev.next = prev.next.next; // prev.next.next
                delNode.next = null;
                // 这里prev不需要后挪，因为删除之后，prev.next节点已经变了，有可能还是val要删除。
            }else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

这里使用虚拟头结点之后，前面的两种对于头结点的特殊处理就都不需要了，因为每个结点都有前一个节点，注意最后return时要return dummyHead的下一个节点。

本机调试

在Solution中创建main函数

public static void main(String[] args) {
        int[] nums = {1,2,6,3,4,5,6};
    }

需要ListNode中有一个构造函数，传入一个arr，创建一个链表。

    /**
     * 链表节点的构造函数
     * 使用arr作为参数，创建一个链表，当前的listNode为链表头结点。
     *
     * @param arr
     */
    public 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;
        }
    }

为了让大家看到链表是什么，改写一下toString方法。

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

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

运行结果:

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

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

运行结果:

Solution类可以有Main函数，但是我们如果连带着main函数提交，会编译出错。我们本地才有数组到listNode的构造函数，但LeetCode中没有。

链表和递归

大家做程序员绕不开递归，递归是组建逻辑很重要的一部分，递归编写抽象逻辑。

可视化算法中随机生成迷宫算法，分形图绘制等都与递归密不可分。推箱子的解也是求递归的过程。高级排序算法使用到递归。

熟练掌握递归是初级程序员和高级程序员的分水岭。

什么是递归？

本质上，将原来的问题，转化为更小的同一问题（小到不能再小）

举例:数组求和

Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])

后面的sum函数要解决的就是比前一个sum更小的同一问题。

Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])

以此类推，直到对一个空数组求和。此时变成了最基本的问题。

Sum(arr[n-1...n-1] ) = arr[n-1] + Sum([])

递归解决数组求和

package cn.mtianyan;

public class Sum {
    public static int sum(int[] arr){
        return sum(arr,0);
    }

    /**
     * 计算arr[l...n)这个区间内所有数字的和,真正的递归函数
     */
    private static int sum(int[] arr,int l){
        if (l == arr.length)
            return 0;
        return arr[l] + sum(arr,l+1);
    }

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

这是我们完成的递归函数，运行结果:

所有的递归算法可以分为两步，第一步是求解最基本问题（最基本问题是不能自动求解的），第二步把原问题转化为更小的问题。

注意递归函数的语义，计算arr[l...n)范围里的数字和,注意递归函数的宏观语义。递归函数就是一个函数，完成一个功能。就把递归函数想成一个子函数。

链表的天然递归性质

递归算法的宏观语义。

可以理解为是0这个节点，挂了一个更短的链表;直到最后NUll本身是一个链表。
使用递归完成LeetCode,删除链表中所有v。

函数本身的宏观语义。

这样就递归的把问题解决了。对更小的问题求解，最后组合成原问题。

package cn.mtianyan;

class SolutionRecusion {

    public ListNode removeElements(ListNode head, int val) {
        if(head == null) // 求解最基本问题
            return null;
        ListNode res = re moveElements(head.next,val); // 将原问题转换为更小问题
        if (head.val == val){
            return res; // 继续调用更小问题求解。
        }else {
            head.next = res; // 这个head不需要删除，继续连接上链表。
            return head;
        }
    }

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

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

这里的代码可以化简为:

head.next = removeElements(head.next,val);
return head.val == val?head.next:head;

递归函数的微观解读

递归调用和子函数调用没什么区别，只不过BC变成了A本身。

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

为了演示方便，我们将最后一句拆成三句。

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

递归函数的调用，本质就是函数调用只不过调用的函数是自己而已

正向箭头调用过去，直到在sum(arr 2)中条件l == n达成，返回0.然后逆着一步一步返回去。

       if(head == null) // 求解最基本问题
            return null;
        head.next = removeElements(head.next,val); // 将原问题转换为更小问题
        return head.val == val?head.next:head;

模拟调用，对6->-7->8->null 删除7

从前往后调用，直到达成条件head == null

程序调用的系统栈; 递归调用是有代价的:函数调用+系统栈空间

递归调用的调试

打印输出调试法，单步跟踪。递归中有一个非常重要的参数的，递归深度。