链表算法专题与技巧

September 1, 2017

链表（Linked List）是计算机科学中最基础且高频的数据结构之一。在算法面试与实际开发中，链表问题主要考察指针操作的缜密程度与边界条件的处理能力。

虚拟头节点（Dummy Head）

核心解决头节点位置变化时怎么记住开头的位置

dummy head（虚拟头节点/哨兵节点）是链表解题中的“神器”。只要涉及到链表的插入、删除、合并、重排，使用虚拟头节点都能极大地简化边界条件处理（例如免去对 head == nil 或头节点改变时的特判）。

链表删除类

LeetCode 203 - 移除链表元素 (Remove Linked List Elements)

难度：简单
典型场景：当头节点本身可能被删除时，普通做法需要单独处理头节点的删除循环。使用虚拟头节点可以统一处理所有节点的删除逻辑。

func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head} // 哨兵节点
    curr := dummy
    
    for curr.Next != nil {
        if curr.Next.Val == val {
            curr.Next = curr.Next.Next // 删除节点
        } else {
            curr = curr.Next
        }
    }
    
    return dummy.Next // 直接返回虚拟节点的下一个
}

合并链表类

LeetCode 21 - 合并两个有序链表 (Merge Two Sorted Lists)

难度：简单
典型场景：合并产生的新链表，一开始不知道谁是头节点。用 Dummy Head 做"地基"，后续直接往下追加节点即可，无需预先比较 l1.Val 与 l2.Val。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            curr.Next = l1
            l1 = l1.Next
        } else {
            curr.Next = l2
            l2 = l2.Next
        }
        curr = curr.Next
    }
    
    if l1 != nil { curr.Next = l1 }
    if l2 != nil { curr.Next = l2 }
    
    return dummy.Next
}

总结：什么时候该用 Dummy Head？

记这几个特征，只要符合任意一个，就直接建立 dummy := &ListNode{Next: head}：

头节点可能被修改/删除（比如删除元素、去重、翻转）。
新链表是从无到有拼接出来的（比如合并链表、按奇偶拆分链表）。
需要频繁操作上一个节点（prev 指针）（比如两两交换、局部翻转）。

链表反转

核心思路：分为prev, curr, next三个指针。 next记住下一部分的头；curr执行反转操作，指向prev；prev记住之前的位置，给curr来更新next

链表反转（Reverse Linked List）是将链表节点的指向逆转（例如原本 1 -> 2 -> 3 -> 4 变为 4 -> 3 -> 2 -> 1）。它是许多复杂链表算法（如回文链表判断、重排链表）的基础子步骤。

迭代法（三指针法）

迭代法是最直观且高效的方法，通过维护 prev、curr、next 三个指针逐步反转指针方向。

核心步骤：
1. next = curr.Next 保存后继节点
2. curr.Next = prev 反转当前节点指向
3. prev = curr; curr = next 前进指针

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for curr := head; curr != nil; {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

递归法

核心为用递归分解完成减一的思想，同时用压栈的方式可以记住prev(head)，curr用head.next来访问，next就直接通过参数传递给方法

递归法将大问题拆解为子问题：“先反转 head.Next 之后的链表，再将当前节点挂到反转后的子链表末尾”。

func reverseListRecursive(head *ListNode) *ListNode {
    // Base case: 空链表或只有一个节点
    if head == nil || head.Next == nil {
        return head
    }
    
    newHead := reverseListRecursive(head.Next)
    // head.Next 此时是子链反转后的尾节点，将它的 Next 指向 head
    head.Next.Next = head
    head.Next = nil
    
    return newHead
}

头插法

也使用dummy Head指向下一个要插入的位置，prev指针指向curr.Next

复杂度分析

方法	时间复杂度	空间复杂度	说明
迭代法	$O(n)$	$O(1)$	只需要常数级别的额外指针空间
递归法	$O(n)$	$O(n)$	隐式使用系统函数调用栈，栈深度为 $n$

判断链表是否有环与寻找入环点

环形链表（Linked List Cycle）是经典的双指针（Floyd 判圈算法 / 快慢指针）应用场景。

检测是否有环

哈希表法：遍历链表并将节点内存地址存入哈希集合，若访问到已存在于集合中的节点则说明有环。
- 复杂度：时间复杂度 $O(n)$，空间复杂度 $O(n)$。
快慢双指针法（Floyd 判圈算法）：
- 定义 slow 指针每次走 1 步，fast 指针每次走 2 步。
- 若链表无环，fast 会率先到达 nil；若链表有环，fast 与 slow 必然在环内相遇（相对速度为每步追赶 1 个节点）。
- 复杂度：时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func hasCycle(head *ListNode) bool {
    fast, slow := head, head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    
    return false
}

寻找环的入口节点（LeetCode 142）

数学推导：

设起点到环入口距离为 $a$，环入口到相遇点距离为 $b$，相遇点继续走回环入口距离为 $c$（环长为 $b + c$）。
相遇时，slow 走的距离为 $a + b$。
fast 走的距离为 $a + n(b + c) + b$（其中 $n \ge 1$ 为快指针绕环圈数）。
由于 $S_{fast} = 2 \cdot S_{slow}$： $$a + n(b + c) + b = 2(a + b) \implies a = (n - 1)(b + c) + c$$
化简得 $a = (n - 1)(b + c) + c$，即 $a \equiv c \pmod{b + c}$。注意相遇时 $n$ 不一定等于 1（$n$ 取决于环长与入环前链长），但上式中的同余关系与 $n$ 无关，恒成立。
因此：相遇后，将一个指针重置到链表头 head，另一个指针保持在相遇点，两者以相同速度 1 前进。head 指针走 $a$ 步恰好到达环入口；相遇点指针走 $a$ 步等价于只走 $c$ 步（多出的 $(n-1)(b+c)$ 均为整圈，相当于回到原位置），而沿环从相遇点走 $c$ 步也恰好回到环入口。两者必然在环入口再次相遇，该位置即为环入口节点！

func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            // 两指针相遇，重置 ptr 从头出发
            ptr := head
            for ptr != slow {
                ptr = ptr.Next
                slow = slow.Next
            }
            return ptr // 入口节点
        }
    }
    
    return nil
}

判断两链表是否相交（LeetCode 160）

方法1. 通过连接l2的头和l1的尾巴，判断是否有环即可（转化为是否有环)

方法2. 双指针对调法

双指针对调法：指针 pA 遍历完链表 A 后转向链表 B 头节点；指针 pB 遍历完链表 B 后转向链表 A 头节点。
若两链表相交，由于 $L_A + L_{common} + L_B = L_B + L_{common} + L_A$，两指针最终会在相交起始节点相遇；若不相交，最终同时到达 nil。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pA, pB := headA, headB
    
    for pA != pB {
        if pA == nil { pA = headB } else { pA = pA.Next }
        if pB == nil { pB = headA } else { pB = pB.Next }
    }
    
    return pA
}