链表

链表 vs 数组

链表和数组都是线性结构，但底层存储方式截然不同，导致各自有不同的操作效率。

操作	数组	链表	说明
随机访问 a[i]	O(1)	O(n)	链表必须从头遍历
头部插入/删除	O(n)	O(1)	链表只需改指针
尾部追加	O(1) 摊还	O(n) 或 O(1)*	*维护尾指针时 O(1)
中间插入/删除	O(n)	O(1)*	*已知节点引用时 O(1)
内存布局	连续	分散	链表有额外指针开销
缓存友好性	好	差	数组利用 CPU 缓存行

单链表：节点定义与基本操作

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next   # 指向下一个节点的引用

# 构建链表 1 → 2 → 3 → None
head = ListNode(1, ListNode(2, ListNode(3)))

# 遍历链表
def traverse(head):
    cur = head
    while cur:
        print(cur.val, end=" → ")
        cur = cur.next
    print("None")

# 在索引 idx 后插入新节点
def insert_after(node, val):
    new_node = ListNode(val)
    new_node.next = node.next   # 新节点指向后继
    node.next = new_node         # 前驱指向新节点

# 删除节点的后继
def delete_next(node):
    if node.next:
        node.next = node.next.next  # 跳过后继节点

虚拟头节点（Dummy Node）

处理链表时，头节点经常是边界情况的来源（删除头节点需要特殊处理）。虚拟头节点是在真实头节点之前添加一个哨兵节点，使所有节点的处理逻辑统一。

# 删除链表中所有值等于 target 的节点
def remove_elements(head, target):
    dummy = ListNode(-1)   # 虚拟头节点，值无关紧要
    dummy.next = head
    cur = dummy

    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next   # 删除
        else:
            cur = cur.next

    return dummy.next   # 返回真实头节点（可能已改变）

# 无需单独处理头节点为 target 的情况！

双向链表与 LRU Cache

双向链表每个节点有 prev 和 next 两个指针。结合哈希表，可实现 LRU Cache（最近最少使用缓存），所有操作 O(1)。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()  # 有序字典 = 哈希表 + 双向链表

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)    # 标记为最近使用
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 淘汰最久未使用的（链表头部）

快慢指针的链表应用

找链表中点

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # 慢指针：每次 1 步
        fast = fast.next.next   # 快指针：每次 2 步
    # fast 到达终点时，slow 恰好在中点
    return slow

Floyd 判圈算法（环检测）

若链表有环，快指针终会追上慢指针（在环内），就像两个跑步者在跑道上最终相遇。

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:    # 快慢指针相遇 → 有环
            return True
    return False

def detect_cycle(head):
    """找到环的入口节点"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # 将一个指针重置到头部，两者以相同速度前进，相遇处即环入口
            # 数学证明：设链头到环入口距离 a，环长 b，相遇点距入口 c
            # 可推导：从头出发和从相遇点出发，走 a 步后同时到达入口
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow  # 环的入口
    return None

链表反转

迭代法

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next    # 1. 保存后继
        cur.next = prev   # 2. 反转指针
        prev = cur        # 3. prev 前移
        cur = nxt         # 4. cur 前移
    return prev  # prev 指向新头节点

递归法

def reverse_list_recursive(head):
    # 基本情况：空链表或单节点
    if not head or not head.next:
        return head
    # 假设 head.next 之后的部分已经反转完毕
    new_head = reverse_list_recursive(head.next)
    # 让 head 的后继节点指回 head
    head.next.next = head
    head.next = None   # 断开原来的连接
    return new_head

合并两个有序链表

def merge_two_lists(l1, l2):
    dummy = ListNode(-1)  # 虚拟头节点简化逻辑
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2   # 连接剩余部分
    return dummy.next
# 时间 O(m+n)，空间 O(1)（迭代法，原地修改指针）

经典题：K 个一组反转链表

LeetCode 25。每 K 个节点为一组翻转，不足 K 个的保持原样。

def reverse_k_group(head, k):
    def reverse(start, end):
        # 反转 start 到 end（不含 end）之间的节点
        prev, cur = end, start
        while cur != end:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev  # 新头节点

    dummy = ListNode(0, head)
    group_prev = dummy

    while True:
        # 找到本组最后一个节点
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next   # 不足 k 个，直接返回

        group_next = kth.next         # 本组后继
        # 反转本组：group_prev.next 到 kth
        new_head = reverse(group_prev.next, group_next)
        group_prev.next.next = group_next   # 原头节点（现尾节点）接后续
        group_prev.next = new_head          # 前驱接新头
        group_prev = group_prev.next.next   # 移动到下一组的前驱位置
        # 等等，这里有问题，让我用更清晰的写法

# 更清晰的版本
def reverse_k_group_v2(head, k):
    dummy = ListNode(0)
    dummy.next = head
    prev_group_tail = dummy

    while head:
        # 检查是否还有 k 个节点
        tail = head
        for i in range(k - 1):
            tail = tail.next
            if not tail:
                return dummy.next
        next_group_head = tail.next
        # 反转这 k 个节点
        prev, cur = next_group_head, head
        for _ in range(k):
            cur.next, prev, cur = prev, cur, cur.next
        # 连接
        prev_group_tail.next = tail  # 连接反转后的头（原来的 tail）
        prev_group_tail = head        # head 现在是这组的尾
        head = next_group_head
    return dummy.next

时间O(n) 空间O(1)