链表算法：反转、快慢指针与合并

重新整理“链表算法：反转、快慢指针与合并”时，我先翻了自己以前的错误记录，其中最典型的一条就是：链表题让我吃过最多的亏不是不会反转，而是改完 next 以后把后面的节点弄丢了，还找不到断在了哪里。沿着这个问题再看原理和代码，比直接背结论清楚得多。

链表算法看起来题型很多，但本质都围绕指针移动和指针重连。链表没有随机访问能力，所以不能像数组一样直接跳到某个下标；它的优势是找到位置后修改连接关系很便宜。

链表题的核心动作

链表算法常见套路

图：链表题最怕断链，修改指针前先保存后继节点

链表题常见技巧：

虚拟头节点：统一处理删除头节点和普通节点。
快慢指针：找中点、判环、找倒数第 k 个。
三指针反转：prev、cur、next。
双链合并：归并两个有序链表。
分段处理：局部反转、分组反转。

反转链表

反转链表最容易犯的错误是先改 cur.next，却忘了保存原来的下一个节点。

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

安全顺序是：

保存 next。
反转 cur.next。
移动 prev。
移动 cur。

删除节点：虚拟头节点

删除链表节点时，如果被删除的是头节点，代码容易多写一堆判断。虚拟头节点可以统一逻辑。

ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    while (cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;
}

注意删除时不要急着移动 cur。如果连续多个节点都要删除，移动过早会漏删。

快慢指针：找中点

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

当链表长度为偶数时，这种写法返回第二个中点。如果业务要第一个中点，需要调整循环条件。

判环：快慢指针相遇

boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

如果存在环，快指针每次比慢指针多走一步，最终一定会追上。这个结论依赖的是相对速度，而不是链表长度。

合并两个有序链表

ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

这里依然用虚拟头节点降低边界复杂度。

复杂度

大多数链表算法时间复杂度是 O(n)，空间复杂度可以做到 O(1)。如果使用递归反转或递归合并，要额外考虑调用栈空间。

我的分析

链表题不是难在算法思想，而是难在指针安全。我的习惯是画出三个节点：前驱、当前、后继。每次修改连接前，先确认是否还需要原来的 next。

工程里链表常作为组合结构的一部分出现，比如 LRU 缓存使用哈希表 + 双向链表，跳表使用多层链表，消息队列和任务链路也经常有链式结构思想。

面试题

为什么链表删除节点常用虚拟头节点？
如何找到倒数第 k 个节点？
如何判断链表是否有环，并找到入环点？
反转链表为什么必须先保存 next？
LRU 为什么需要双向链表，而不是单向链表？