Singly linked list（单链表）- 1

2021-07-20

1. 单链表

Reference: 递归反转链表的一部分

目标：练习单链表的题目是为了训练递归思维，对递归有个直观的认识。

单链表的结构

// 单链表节点的结构
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

2. 递归思路

为什么可以用递归？

大问题可以拆成两个子问题（head 和剩余部分的反转）
子问题的求解方式和大问题一样（也是 head 和剩余部分的反转）
存在最小子问题

代码实现

ListNode reverse(ListNode head) {
    if (head.next == null) return head; // base case
    ListNode last = reverse(head.next); // recursive
    head.next.next = head;
    head.next = null;
    return last;
}

这个 reverse function 是干嘛的呢？

只要输入节点 head，将会把以 head 为起点的链表进行反转，并且返回反转后的 head 节点。

Base case

递归必须需要有 base case，它是我们的最小子问题，也是递归的结束点，在这个例子里就是「只有一个节点的时候直接返回自己」。

图解

这个视频讲的很清晰：递归实现 (qq.com)

总的来说，我们要先进行「递」的操作，也就是下图右边的箭头，我们不断的重设 head 节点，并传递到下一层。

到了最后一层（base case）的时候，我们开始进行「归」的操作。

base case 只有一个 head node，所以我们直接返回这个 head node。

倒数第二层，我们的 head node = 78，head.next = 99，我们的目标是让 head node = 99，head.next = 78。

怎么做到这个反转呢？

首先，我们要让 99 指向 78，也就是 head.next.next = head；

接着，因为 78 现在是最后一个 node，它的 next 应该是 null，于是我们进行 head.next = null 的操作。

注意顺序！！！

我们必须先让 99 指向 78，再重设 78 的 next，不然 78 和 99 之间就没法建立起关系了（它俩唯一的联系就是 78.next = 99）。

复杂度比较

递归解法：时间复杂度 = O(N)，空间复杂度 = O(N)

迭代解法（本文暂不分析）：时间复杂度 = O(N)，空间复杂度 = O(1)

递归思路的空间复杂度更高，因为需要堆栈，所以考虑效率的话还是用迭代算法更好。

3. 关于递归的思考

想要判断一个问题是否能用递归解决，我们必须知道 base case（最小问题）以及大问题和小问题之间的递进关系。

也就是说，先从底层开始思考，再向上移动两层，看看这个问题是不是可以重复用同一个方式来解决，如果可以的话，就可以用递归~

递归都是这个思路：先看边界条件怎么解。在这个问题中就是只有一个 node 的情况。第 2 行就处理了。然后假设 n-1 的情况函数已经能处理了，该如何解决 n 的情况，也就是第 4 和第 5 行。

Luna Tech