算法刷题系列（十一）：链表——节点引用与指针重连

算法刷题系列（十一）：链表——节点引用与指针重连

前面的栈和队列说明了如何管理“下一步要处理谁”；链表关注的是另一件事：节点之间如何通过引用连接。数组靠连续下标访问元素，链表则从一个节点沿着 next 引用逐个走到后续节点。

本篇从单向链表的结构开始，用“删除所有指定值的节点”和“反转链表”两个原创例子练习引用重连，并介绍虚拟头节点如何统一处理头节点边界。Java 与 Python 示例都包含可运行的节点定义和测试。

一、数组与链表的区别

数组按下标访问元素：

index:  0   1   2   3
value:  7   4   9   2

单向链表由节点和引用组成：

head
  │
  ▼
 [7] → [4] → [9] → [2] → null

每个节点保存两部分：

• value：节点的数据；
• next：指向下一个节点的引用；尾节点的 next 为 null。

两种结构的主要差别：

操作	数组	单向链表
按下标读取	O(1)	从头遍历，O(n)
搜索某个值	O(n)	O(n)
已知前驱后插入/删除	通常要移动元素，O(n)	修改少量引用，O(1)
额外结构成本	较低	每个节点还要存 next 引用

注意，“链表插入和删除是 O(1)”有前提：必须已经拿到待操作位置的前驱节点。若还要先从头查找该节点，查找本身仍然需要 O(n)。

二、定义单向链表节点

一个简单的节点结构可以写成：

Node:
    value
    next

head 指向首节点。空链表中 head 为 null/None。如果操作会删除或替换头节点，通常需要单独处理头部，或者增加一个虚拟头节点。

三、例子一：删除链表中所有指定值

给定链表：

4 → 2 → 4 → 3 → 4 → null

删除所有值为 4 的节点后，结果为：

2 → 3 → null

1. 为什么头节点容易成为边界问题？

如果头节点的值正好是待删除值，就需要把 head 移到下一个节点。若连续多个头节点都要删除，还要反复更新 head。

例如：

4 → 4 → 2 → null

一种处理方式是先用循环跳过所有待删除头节点，再处理其余部分。另一种更统一的方式是建立虚拟头节点：

dummy → 4 → 2 → 4 → 3 → 4 → null

这样，原头节点也变成了普通节点 dummy.next。每次只看当前节点的后继：

• 若 current.next.value 等于目标值，把 current.next 跳过；
• 否则将 current 前进到 current.next。

删除时 current 不前进，因为新接到它后面的节点也可能需要删除。

四、Java 实现：删除指定值

public class LinkedListAlgorithms {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode removeValue(ListNode head, int target) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.value == target) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return dummy.next;
    }

    public static ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }

        return previous;
    }

    public static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return dummy.next;
    }

    public static String toString(ListNode head) {
        StringBuilder result = new StringBuilder();
        for (ListNode current = head; current != null; current = current.next) {
            if (result.length() > 0) {
                result.append(" -> ");
            }
            result.append(current.value);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        ListNode head = fromArray(4, 2, 4, 3, 4);
        head = removeValue(head, 4);
        System.out.println(toString(head)); // 2 -> 3
        System.out.println(toString(reverse(head))); // 3 -> 2
    }
}

删除操作只改变 next 引用，不需要搬动后续节点的值。被跳过的节点不再从返回链表可达；在 Java 中，若没有其他引用指向它，后续由垃圾回收器处理。

五、例子二：反转单向链表

反转前：

1 → 2 → 3 → null

反转后：

3 → 2 → 1 → null

在遍历时，维护三个引用：

• previous：已经反转好的前半段头节点；
• current：当前正要处理的节点；
• nextNode：提前保存当前节点原来的后继。

每一步的顺序必须是：

1. 先保存 current.next；
2. 将 current.next 指向 previous；
3. 将 previous 前进到 current；
4. 将 current 前进到之前保存的 nextNode。

如果在保存 nextNode 前就改写 current.next，原链表后半段就失去入口，无法继续遍历。

六、Python 实现：删除与反转

from __future__ import annotations

class ListNode:
    def __init__(self, value: int, next_node: "ListNode | None" = None):
        self.value = value
        self.next = next_node

def remove_value(head: ListNode | None, target: int) -> ListNode | None:
    dummy = ListNode(0, head)
    current = dummy

    while current.next is not None:
        if current.next.value == target:
            current.next = current.next.next
        else:
            current = current.next

    return dummy.next

def reverse(head: ListNode | None) -> ListNode | None:
    previous = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    return previous

def from_values(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next

def to_values(head: ListNode | None) -> list[int]:
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values

head = from_values([4, 2, 4, 3, 4])
head = remove_value(head, 4)
assert to_values(head) == [2, 3]
assert to_values(reverse(head)) == [3, 2]
assert to_values(remove_value(from_values([4, 4]), 4)) == []
assert to_values(reverse(from_values([]))) == []
assert to_values(reverse(from_values([7]))) == [7]

七、复杂度与正确性

删除指定值时，每个节点最多检查一次：

• 时间复杂度：O(n)；
• 额外空间复杂度：O(1)。

反转链表也只遍历一次，并原地改写每个节点的 next：

• 时间复杂度：O(n)；
• 额外空间复杂度：O(1)。

反转过程中可以维持一个不变量：每轮循环开始时，previous 指向的链表已经是原链表已处理前缀的反转结果，current 指向尚未处理部分的首节点。循环结束时 current 为空，previous 就是新链表的头节点。

八、常见错误

1. 删除头节点时忘记更新 head：使用虚拟头节点可以统一删除逻辑。
2. 删除后仍推进 current：连续重复值可能被跳过；删除后应留在前驱位置继续检查。
3. 反转前没有保存 next：改写引用后可能丢失未处理部分。
4. 返回旧头节点：反转后旧头节点变成尾节点，新头节点是 previous。
5. 把节点值交换当作链表反转：题目通常要求调整节点连接；若节点还有身份或外部引用，交换值并不等价。
6. 认为任意链表插入都为 O(1)：只有已知插入位置的前驱节点时，重连引用才是常数时间。
7. 遍历时意外形成环：修改 next 前应先确认原后继已保存，调试时可用访问计数防止无限循环。

九、数组、链表与队列的联系

队列可以用链表实现：队尾插入、队头删除，只要同时保存头尾引用，通常都能在 O(1) 完成。数组实现则需要循环数组来避免出队时整体搬移。

但是链表并不会自动优于数组：

• 需要频繁按下标访问时，数组更合适；
• 需要在已知节点附近频繁插入/删除时，链表更方便；
• 链表每个节点有引用开销，且遍历时缓存局部性通常不如连续数组。

选择结构时应根据操作模式，而不是只看单个操作的复杂度。

十、小结

单向链表的核心是节点引用，而链表题的核心常常是安全地重连引用。删除节点时要想清楚前驱如何接到后继；反转时要先保存后续节点再改写方向。虚拟头节点能简化头部删除，三个引用则足以原地反转整条链表。

下一篇将学习双指针：两个索引或节点如何按特定规则协同移动，从而减少重复遍历。