4. 链表核心操作与变形

链表题在算法面试中占据独特地位：它不像数组那样可以随机访问，也不像树那样有递归的结构美感，却几乎覆盖了指针操作、边界处理、空间换时间等所有基础考点。本节围绕反转、合并、环检测、交点、复制带随机指针链表、K个一组翻转、链表排序七类高频题型展开，重点讲清“每一步指针到底指向哪里”以及“工程实现中容易踩的坑”。

一、反转链表：迭代与递归的取舍

反转单链表是链表操作的“hello world”。给定 1→2→3→4→5→null，目标是 5→4→3→2→1→null。迭代法的核心是维护三个指针：prev（已反转部分的头）、curr（当前待处理节点）、next（暂存后继）。每轮执行四步：暂存 next = curr.next；断开并反向 curr.next = prev；prev = curr；curr = next。循环结束时 prev 即为新头节点。

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

递归写法更简洁，但要注意递归深度等于链表长度，长链表可能栈溢出。面试中若链表长度未知，优先迭代。一个常见变形是“反转前 N 个节点”或“反转区间 [m, n]”，此时需要先定位到第 m-1 个节点，记录其前驱，再对区间内做局部反转，最后把三段接回去。边界判断集中在 m == 1 时头节点会变化，通常引入哑节点（dummy）统一处理。

二、合并两个有序链表与 K 路归并

合并两个有序链表的标准做法是双指针加哑节点：比较 l1.val 与 l2.val，把较小者接到结果尾部，指针后移，直到一方为空，再把剩余部分整体接上。哑节点避免了“结果链表头节点是谁”的分支判断，是链表题中极高频的技巧。

def merge_two(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

当题目升级为“合并 K 个有序链表”时，朴素两两合并的时间复杂度是 O(KN)，而用最小堆维护 K 个当前头节点可降到 O(N log K)。堆中存 (val, index, node)，因为 Python 的 heapq 在值相等时会比较第二个元素，直接存节点可能报错。每弹出一个节点，就把它的后继压入堆，直到堆空。

三、环检测与交点：快慢指针的两种用法

判断链表是否有环，用 Floyd 判圈法：慢指针每次走一步，快指针每次走两步。若存在环，两者必在环内相遇；若快指针走到 null，则无环。找到环入口的推导是面试常问点：设头到入口距离为 a，入口到相遇点为 b，相遇点回到入口为 c。相遇时快指针走了 a + b + n(b + c)，慢指针走了 a + b，由 2 倍关系可得 a = c + (n-1)(b + c)。因此从相遇点和头节点同时出发，再次相遇处即为环入口。

“两个链表的交点”是另一类经典题。若两链表相交，则从交点起尾部完全重合。做法是先各求长度，让长链表先走长度差，再同步前进，第一个相同节点即为交点。注意判断的是节点引用相同，而非值相同。若题目允许修改结构，也可用哈希表存已访问节点，但空间 O(N)；双指针法空间 O(1)，更受面试官青睐。

四、复制带随机指针的链表

题目要求深拷贝一个节点包含 next 和 random 两个指针的链表。难点在于 random 可能指向尚未创建的节点。常用两种解法：

哈希表法：第一遍遍历原链表，为每个节点创建副本并存入 map[old] = new；第二遍遍历，设置 new.next = map[old.next]、new.random = map[old.random]。时间 O(N)，空间 O(N)。

原地拼接法：把副本节点插到原节点之后，形成 A→A'→B→B'。然后设置 A'.random = A.random.next（若 A.random 非空）。最后拆分成两条链表。空间 O(1)，但指针操作更易出错，建议画图逐步验证。

五、K 个一组翻转链表

这是反转与分组的结合。给定 1→2→3→4→5，k=2，结果为 2→1→4→3→5。实现步骤：先检查剩余节点是否够 k 个，不够则保持原样；对每 k 个节点做局部反转；用 group_prev 记录上一组的尾节点，反转后把它接到新头，并更新下一组的起点。

def reverse_k_group(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
        group_next = kth.next
        prev, curr = group_next, group_prev.next
        while curr != group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp

关键细节：反转时 prev 初始化为 group_next，这样第一组的尾节点自然指向下一组的头。循环结束后 group_prev 更新为原组头，也就是反转后的尾。

六、链表排序：归并是首选

链表排序在面试中通常要求 O(N log N) 时间、O(1) 空间。由于链表不支持随机访问，快排的分区代价高，归并排序成为最优解。自顶向下归并用快慢指针找中点，递归排序左右两半，再合并；自底向上归并则从长度为 1 的子链表开始两两合并，逐步扩大步长，避免递归栈空间。

找中点时，快指针从 head.next 出发可让慢指针停在左半部分末尾，便于断开。若快慢都从 head 出发，偶数长度时慢指针会偏右，需要额外处理。合并阶段复用前面的 merge_two 即可。

七、工程实现细节与调试清单

链表题的错误往往不在算法，而在指针操作顺序和边界。以下清单可直接用于自测：

检查项	常见错误	验证方式
空链表 / 单节点	未判空直接访问 head.next	输入 None、单节点各跑一次
哑节点使用	返回 head 而非 dummy.next	头节点被修改的用例
指针丢失	先改 curr.next 再存 next	画图逐步跟踪
环导致死循环	未在合适位置断开	加步数上限或快慢指针检测
random 为空	未判 random is None	构造 random 为空的用例

调试时建议在纸上画出节点和指针箭头，每执行一步就更新图。对于 K 个一组翻转、复制随机指针这类多指针题，先写出“操作前状态”和“操作后状态”，再对照代码逐行验证。面试中如果一时写不对，可以先讲清思路和边界处理，再补代码，通常比沉默写错更有效。

链表题的核心能力是“在有限指针下维护不变量”。反转维护的是“prev 之前已反转”，合并维护的是“dummy 到 tail 已有序”，环检测维护的是“快慢指针速度差”。抓住不变量，边界和指针顺序就有了判断依据。