数据结构-链表和递归

移除链表元素

这节我们通过移除链表元素这个问题来开始探讨链表和递归的关系。

按照LeetCode上的要求我们在不使用虚拟头节点的时候的代码

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;
            } else
                prev = prev.next;
        }

        return head;
    }
}

现在我们加上虚拟头结点试下

class Solution {
    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 = delNode.next;
                delNode.next = null;
            } else
                prev = prev.next;
        }
		
        // 需要返回真正的头结点
        return dummyHead.next;

    }
}

通过上面这个 我们清楚了虚拟头结点的主要作用就是统一了头结点和其他节点的操作。达到简化逻辑的目的。

抒写自己的测试代码

上面我们写的代码可以直接放到LeetCode进行执行，但是不可以本地测试。如果我们想本地测试需要进一些编写。

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

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

    // 以当前节点为头结点的链表信息字符串
    @Override
    public String toString() {

        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val + "->");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }

}

我们在链表的节点类构造函数中，新增将数组变为链表的功能。

在Solution类中进行测试

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);
}
// 结果
1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL

在其他题目中，我们可以按照这种思想进行编写测试。

递归的基础和递归的宏观语意

本质上递归就是将原来的问题转化为更小的同一个问题。

例如数组求和

我们将上面的过程写成代码

public class Sum {

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

    // 计算arr[l...)这个区间内所有数字的和
    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};
        System.out.println(sum(nums));
     }

}

分析一下递归的代码结构，大致分为下面两个部分

递归函数本身也是一个函数，完成一个功能。