链表的逻辑：BeyondCRUD

链表是一个理解起来并不复杂、但是写起来很容易犯错、思考复杂起来时却觉得“没那么简单”的数据结构。但是，不管它简单还是复杂，以一个清晰、渐进的逻辑理解它，总归还是必要的。

数据结构，本质上是保存数据、利用数据的载体，本质都要回归到CRUD（增删改查）上。而理解一个数据结构，都应该从定义、结构出发，先把基本的CRUD操作作为“套路”熟悉、掌握了，再稍微融会贯通、灵活运用，这样，使用好一个数据结构解决基本问题，也就没那么复杂而缺乏头绪了。

对于一个需要被计算机解决的算法问题，本质上都需要以下几步：

1. 组织信息：如何收集并存储可能有用的数据；

2. 构建信息：如何查询并组织已有的数据；

3. 创造条件：针对具体的算法问题，合理地筛选并处理已有的信息；

4. 进行计算：根据一些经过“预处理”的数据，得到需要求解的结果并返回。

链表的定义

链表(linked list)是一种线性表，也就是说，其中的数据是有一定顺序的，但是不同于数组的是，链表在内存空间中不是连续存储的。当你手上已有一个节点时，为了寻找下一个节点，都是通过访问其保存的指针节点。

链表的好处在于，不必预先知道需要分配的空间的总大小，因为链接的保存方式都是利用前一个节点指向的指针，因此增加、删除时会比较方便。

所以，在LeetCode等平台上，往往定义一个链表的方式，都是给定一个头节点，定义如下：

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

根据这样的定义，我们其实就能总结出几条重要的使用原则：

1. 如果当前指针变成了null，就不能再利用类似于curr.next这样的判断条件了，会报空指针的错误，因此，可以考虑使用dummy虚指针这样的办法解决；

2. 当需要修改指针指向时，如果这个指针指向的位置还需要使用，则在修改之前，必须使用一个别的变量进行保存；

3. 当涉及的修改比较复杂时，比如说翻转两个节点，仅仅使用一个指针来进行修改，由于其只能对应自身和自身的指针两个信息，往往不够用，所以可以考虑使用两个甚至多个指针同时进行存储和修改；

4. 此外，使用快慢节点时，尤其是寻找中点、环时的”两倍速度“的快节点，需要注意分奇偶类讨论，因为条件往往不同。

链表的CRUD之增

一般来说，链表的增加节点并不复杂，实际上只需要先保存当前节点的后续节点，将当前节点指向需要被添加的节点，再将需要被添加的节点指向后续节点（当然，也可以先指向后续节点，再修改当前节点的指针）。如果随意修改，有可能会因为链表断开，损失信息（反复思考链表的定义与组织结构，是个好习惯）。

public void addListNode(ListNode curr, ListNode newNode){
    ListNode nextNode = curr.next;
    curr.next = newNode;
    newNode.next = nextNode;
}

不过，毕竟仅仅这样增加节点的用法太trivial了，一些特殊情况下的插入，或者考虑考虑两个、多个链表的合并，可以认为是较为复杂的”增“操作。

一种比较复杂的操作可见leetcode 708 insert into a sorted circular linked list，这题的问题在于，需要分类讨论三种情况：

1. 中间点：curr.val <= insert && curr.next.val > insert

2. 头结点或者尾结点：curr.val > curr.next.val && (头: curr.val <= insertVal || 尾: curr.next.val >= insertVal)

3. 一种特殊情况，一共就一种结点，但是，是否全程仅有这一个节点，又不能确定，因此必须先遍历一遍，再考虑

class Solution {
    public Node insert(Node head, int insertVal) {
        Node newNode = new Node(insertVal, null);
        if(head == null){
            newNode.next = newNode;
            return newNode;
        }
        Node curr = head;
        do{
            // 判断满足中间点或者头/尾节点的情况，判断终止条件是全部遍历一遍
            if((curr.val <= insertVal && insertVal <= curr.next.val) || (curr.val > curr.next.val && (insertVal <= curr.next.val || insertVal >= curr.val))){
                newNode.next = curr.next;
                curr.next = newNode;
                return head;
            }
            curr = curr.next;
        } while(curr != head);
           // 遍历了一遍之后，还是没有找到，说明只能是特殊情况，
        newNode.next = curr.next;
        curr.next = newNode;
        return head;
    }
}

当然，这种讨论算得上是比较麻烦的了，一般而言，只是讨论奇偶节点以确定条件，算是链表最常见的题型。

现在我们重新回到合并问题，实际上两个链表合并是一个很轻松愉快的操作，利用虚节点建立一个新的列表，然后一一向前比较连接即可：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode head = new ListNode(0);
        ListNode tail = head;

        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                tail.next = l1;
                l1 = l1.next;
                tail = tail.next;
            } else{
                tail.next = l2;
                l2 = l2.next;
                tail = tail.next;
            }
        }
        if(l1 != null) tail.next = l1;
        if(l2 != null) tail.next = l2;
        return head.next;
    }
}

合并链表有什么用呢？其实拿它稍作改进，就可以用于链表排序了，比如leetcode 148题的Sort List，下文描述完“寻找中点”方法之后，将合理做一个呈现。

对于合并K个链表，尽管我们也可以不断重复合并两个链表的操作，但是如果每一次都把新链表加入第一个，实际上比较、运算的长度会越来越长，因此考虑使用一个分治法，先各自归并，再汇合，能将复杂度系数N降低为logN。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;

        int interval = 1;
        while(interval < lists.length){
            for(int i = 0; i + interval < lists.length; i = i + interval * 2){
                lists[i] = mergeTwo(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }

    public ListNode mergeTwo(ListNode l1, ListNode l2){
        // 代码同上述mergeTwoLists
    }
}

虽然多使用了一个分治的想法，但是依旧可以看出，支撑这个问题的基础操作，依旧是普通的合并。

因此，看似复杂的题目，实际上都可以化归到基础操作，再进行一定改良、变化。

使用虚节点保存的想法，可以用于很多地方，同时，断开部分节点再连接，也是很合理的操作，例如leetcode 86 Partition List。

这题实际上不很复杂，就分别取两个新表，一个保存小于x，一个大于x，但是由于不存在一定大于x或者小于x的道理，想像上题一样不用空间不能直接套用到。

当分别建表好了之后，把第一个的尾结点接到第二个表的头结点。

一个可能会错的点：第二个表遍历完成后，要把它的尾结点自己赋予一个null:

public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
        // 建立两个新表的表头以及指针
        ListNode less = new ListNode(0);
        ListNode lesscurr = less;
        ListNode more = new ListNode(0);
        ListNode morecurr = more;
        // 不断向前遍历表
        while(head != null){
            if(head.val < x){
                lesscurr.next = head;
                lesscurr = lesscurr.next;
            } else{
                morecurr.next = head;
                morecurr = morecurr.next;
            }
            head = head.next;
        }
        // 注意，第二个表必须自己将其指向null，否则表中会出现环
        morecurr.next = null;
        lesscurr.next = more.next;

        return less.next;
    }

链表的CRUD之删

其实，链表的另外一个优点就是方便修改、删除。一旦我们根据某个特征，确定了某节点应该被删除，即有两种办法删除它（一般来说，后者更常用些）。

第一种办法来自有点“臭名昭著”的LeetCode 237 Delete Node in a linked list, 这题的意思是，如果只给定当前节点（且保证其不是尾节点），如何原地“删除”当前节点？

其实并不复杂，使用“值传递”的想法，把当前节点的值改为下一个节点的值，然后直接跳过下一个节点就行。（链表不能提供当前节点的上一个节点，所以在这种情况下，直接使用值传递不失为一种办法；但是，在实际系统中，一个node往往包含的信息太多，做一个deep copy往往没这么容易）

public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

当然，这种方法比较非正统一点（因为在实际应用中，往往一个节点拥有的信息很多，不便于一一复制，且有可能破坏其与用户的一一对应的安全性等等），正常的删除当然是结合某个feature，利用一下其pre的节点协助删除了，比如leetcode 203:

删除实际上只需要一个指针就够了，先设立一个虚节点在头部，然后依次向后遍历，如果值与目标相等，则直接将指针指向下一个；如果不相等，则可以将当前指针向后移动一个。

public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while(pre.next != null){
            ListNode curr = pre.next;
            // 若为符合的值，直接将pre节点指向下一个节点
            if(curr.val == val){
                pre.next = curr.next;
            } else{
                // 若不符合，向前移动
                pre = pre.next;
            }
        }

        return dummy.next;
    }

链表的CRUD之查与改：快慢指针

关于链表的修改，显然你得先查找，而查找的目的，一般也是为了找到具有特定特征的节点，进行删除或者修改等操作。

在链表问题中，有两类特殊的查找：一是链表中点的查找，二是链表是否存在环的判断与环入口的查找。

对于链表的中点问题，我们一般考虑使用快慢指针的办法。快指针一次从头节点运动两个节点，慢指针运动一个节点。这样，当快指针运动到末尾时，慢指针恰好到达中点。解题的要点，防止条件出现空指针的情况的关键，主要是分奇数偶数的情况讨论：奇数时结束条件应为fast.next == null，偶数时为fast == null，因此循环条件即为：fast != null && fast.next != null。

public ListNode middleNode(ListNode head) {
        if(head == null) return null;

        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

对于环的检测也不难：最简单的想法是，用hashset保存已经访问过的节点，如果能再遇到一次，说明有环，反之没有。

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        HashSet<ListNode> set = new HashSet();

        ListNode curr = head;
        set.add(head);

        while(curr != null){
            curr = curr.next;
            if(set.contains(curr)){
                return true;
            }
            set.add(curr);
        }

        return false;
    }

如果链表中含有环，快指针必能在绕环时，重新追及到慢指针；如果快指针正常达到末尾的null，说明没有环。

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }

        return false;
    }

如果还需要寻找环的入口，根据简单的数学原理分析，实际上快指针慢指针相遇位置，多出的就是一个从head到入口的位置。所以相遇第一次后，让快指针和头节点一起相向运动，相遇点就是入口：

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

        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null && slow != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }

        if(fast == null) return null;

        while(fast != null && fast != head){
            fast = fast.next;
            head = head.next;
        }

        return fast;
    }
}

当然了，快慢指针的想法，还可以推广至一些有固定关系的情况，比如说LeetCode 19 Remove Nth Node from end of list，求倒数第n个节点。

本题其实不困难，主要也就一个快慢指针而已，只需要先让快指针多跑n + 1步，然后将慢指针指向后两位即可。

唯一的问题是，如果直接从head开始做的话，在n跟list一样长时，容易全部删除，导致出现null的报错，建议是使用一个虚节点dummy，这样保证新的list一定不会被删空。

public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || n <= 0) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        for(int i = n; i >= 0; i--){
            fast = fast.next;
        }
        ListNode slow = dummy;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummy.next;
    }

链表的CRUD之查与改：链表翻转的迭代法与递归法

链表题里还有一个很重要的技巧：翻转链表。虽然翻转链表基础操作是对于整个链表的操作，但是通过适当断开节点，翻转后再重新连上的小技巧，实际上这个题目也可以变为翻转一部分链表。本节我们以这个为例，讲解如何做一些合理的“灵活运用”。

基础操作是LeetCode206 reverse linked list，也就是给定一个链表的头节点，返回一个翻转后的链表的头节点。

iterative 迭代法：

其实就一个点需要关注：结束条件，如果当curr == null才结束，则curr保存不了翻转后的头节点(返回pre即可)，但是如果用curr.next == null，最后一个节点的后续节点实际上还没有连接，需要再连接一次。

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode curr = head;

        while(curr.next != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        curr.next = pre;

        return curr;
    }

迭代法的优势在于，结束条件便于控制。

所以对于leetcode 92 reverse linked list II来说，要求只翻转从第m个到第n个节点，就便于控制条件了：

本题需要注意的问题有二：一则：你需要在需要移动的节点之前，使用一个虚节点做pre，然后更新并向前，且逆序时，应使用pre.next，而非curr来作新逆序节点的队头；二则：最终应该返回dummy.next（虚节点的下一个位置），如果返回的是head，有可能已经被逆序了，会在m = 1的时候报错。

public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 0; i < m - 1; i++){
            pre = pre.next;
        }
        ListNode curr = pre.next;
        for(int i = m; i < n; i++){
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummy.next;
    }

recursive 递归法：

递归的本质是把问题“一视同仁”，也就是说，不管什么大小的问题，其操作方法都一样。这题也是，实际上对于每一个节点，需要做的就是把它的后续节点指向它自己，然后再把它自己指向null（以断开连接，否则会形成环），最终需要返回的是翻转后的头节点。

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        // 获取翻转后的头节点
        ListNode next = reverseList(head.next);
        // 将后序节点指向自己
        head.next.next = head;
        // 将自己的指向断开，连接到null
        head.next = null;

        // 返回处理完了之后的头节点
        return next;
    }

递归法的好处在于清晰简洁，函数的功能定义很清楚，所以拿类似的想法解决一些“大问题与小问题同构”的问题，会非常合适，哪怕那个问题很复杂：

比如说leetcode 25 Reverse Nodes in k-Groups，以k个为一组翻转链表，且不满k个时，不翻转：

其实这题也是一个“同构”的问题，注意递归出口：先向前运动k步，如果中途就没达到，直接返回head节点。然后断开节点，翻转。

public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null) return head;

        ListNode curr = head;

        // 从head运动k - 1步，寻找到第k个node，如果中途就没有，直接返回head，作为离开recursion的条件
        for(int i = k; i > 1; i--){
            curr = curr.next;
            if(curr == null){
                return head;
            }
        }
        // 找到第k个点后，考虑从这里翻转链表，但是需要先将链表在这里断开，否则使用reverse函数翻转的节点就不止k个了
        ListNode next = curr.next;
        curr.next = null;

        // 反转链表，很基本的操作了
        ListNode new_head = reverse(head);

        head.next = reverseKGroup(next, k);
        return new_head;
    }

    public ListNode reverse(ListNode head){
        // 同上，任意一种翻转链表函数均可以
    }

实际上，有了翻转链表的方法，解决LeetCode 234 palindrome linked list也不难了：判断一个链表是不是回文串，其实就结合了上面的寻找中点以及翻转链表的想法：把链表从中点断开，将后半翻转，再一一对比节点的值，看是否相同。

本题需要考虑一下奇数和偶数情况下的条件：fast.next == null 以及 fast.next.next == null。

public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;

        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 找到后半的开头
        ListNode h2 = slow.next;
        slow.next = null;
        // 反转后半链表
        ListNode reverse_h2 = reverse(h2);
        // 逐个比较值
        ListNode p1 = head, p2 = reverse_h2;
        while(p1 != null && p2 != null){
            if(p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }

        // 如果都没问题，返回true
        return true;
    }

    public ListNode reverse(ListNode head){
           // 同上述翻转链表函数
    }

链表部分大致就是这样：一则需要基础扎实，把各种基础操作搞得非常熟练，这样一看到题目就能将基础操作稍微改变、组合，就能解决较难的题目了；二则需要关注各种边界和条件的设计，所以利用虚节点、关注奇数偶数个节点的分类讨论，往往是容易出错的地方。做出思路不难，做到bug-free，还是得多练多反思。

所谓的基础操作，其实不外乎上面提到的各种CRUD。但是，“运用之妙，存乎一心”，合理灵活应用，同时注意新题目的新要求，关心各种边界条件，链表总归是不大难的。