链表

本章目标：掌握链表的核心技巧——虚拟头节点、翻转、快慢指针，能独立解决所有中等链表题。

你将学到

• 单链表、双向链表、循环链表的结构
• 虚拟头节点（Dummy Head）技巧
• 链表翻转（迭代 + 递归）
• 快慢指针（找中点、判环、找环入口）
• 有序链表合并与归并排序
• 回文链表判断

1. 概念

链表与数组互补：数组随机访问 O(1) 但插入删除 O(n)，链表插入删除 O(1)（已知位置）但访问第 k 个元素 O(n)。链表节点在内存中不连续，通过指针连接。

链表题目的核心难点在于指针操作容易出错，尤其是边界条件（空链表、单节点、尾节点）。虚拟头节点是处理这类问题的利器：在真实头节点前加一个哨兵节点，统一了头部和中间的操作。

2. 核心模板

链表定义与虚拟头节点

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) { self.val = val; self.next = nil }
}

// 虚拟头节点模板：统一处理头部的删除/插入
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    var prev: ListNode = dummy
    while let curr = prev.next {
        if curr.val == val {
            prev.next = curr.next
        } else {
            prev = curr
        }
    }
    return dummy.next
}

翻转链表（迭代）

func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var curr = head
    while curr != nil {
        let next = curr!.next
        curr!.next = prev
        prev = curr
        curr = next
    }
    return prev
}

翻转链表（递归）

func reverseListRecursive(_ head: ListNode?) -> ListNode? {
    guard let head = head, head.next != nil else { return head }
    let newHead = reverseListRecursive(head.next)
    head.next!.next = head
    head.next = nil
    return newHead
}

快慢指针（判环 + 找环入口）

// Floyd 判圈算法
func detectCycle(_ head: ListNode?) -> ListNode? {
    var slow = head, fast = head
    // 第一阶段：快慢相遇
    while fast != nil && fast!.next != nil {
        slow = slow!.next
        fast = fast!.next!.next
        if slow === fast {
            // 第二阶段：找入口
            var p = head
            while p !== slow {
                p = p!.next
                slow = slow!.next
            }
            return p
        }
    }
    return nil
}

复杂度

• 翻转链表：时间 O(n)，空间 O(1)（迭代）/ O(n)（递归栈）
• 判环：时间 O(n)，空间 O(1)

3. 经典题目精讲

LeetCode 21 · 合并两个有序链表

题意：将两个升序链表合并为一个新的升序链表。

思路：双指针逐个比较，用虚拟头节点简化头部处理。

func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    var tail: ListNode = dummy
    var l1 = list1, l2 = list2
    while l1 != nil && l2 != nil {
        if l1!.val <= l2!.val {
            tail.next = l1
            l1 = l1!.next
        } else {
            tail.next = l2
            l2 = l2!.next
        }
        tail = tail.next!
    }
    tail.next = l1 ?? l2
    return dummy.next
}

LeetCode 234 · 回文链表

题意：判断链表是否回文。要求 O(n) 时间 O(1) 空间。

思路：快慢指针找中点，翻转后半部分，双指针比较，最后恢复。

func isPalindrome(_ head: ListNode?) -> Bool {
    guard head != nil else { return true }
    // 1. 快慢指针找中点
    var slow = head, fast = head
    while fast != nil && fast!.next != nil {
        slow = slow!.next
        fast = fast!.next!.next
    }
    // 2. 翻转后半部分
    var secondHalf = reverseList(slow)
    let firstHalf = head
    // 3. 比较
    var p1 = firstHalf, p2 = secondHalf
    var result = true
    while p2 != nil {
        if p1!.val != p2!.val { result = false; break }
        p1 = p1!.next
        p2 = p2!.next
    }
    // 4. 恢复（可选）
    _ = reverseList(secondHalf)
    return result
}

4. 易错点

• ⚠️ 翻转链表时 curr.next = prev 和 curr = next 的顺序不能反
• ⚠️ 快慢指针找中点时，链表长度奇偶性会导致中点偏移，需根据题意调整
• ⚠️ Swift 中链表节点是引用类型，用 === 比较身份而非 ==
• ⚠️ 删除节点后注意没有强引用持有它（ARC 会自动回收）

5. 推荐刷题清单

题号	题名	难度	关键
21	合并两个有序链表	Easy	虚拟头节点
141	环形链表	Easy	快慢指针
142	环形链表 II	Medium	Floyd 算法
206	反转链表	Easy	翻转模板
234	回文链表	Easy	快慢+翻转
328	奇偶链表	Medium	双指针重组
148	排序链表	Hard	归并排序

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)