链表：结构与常见操作

链表是一种线性数据结构。每个节点保存数据和指向其他节点的指针，节点在内存中不要求连续存放。本文使用单向链表，并统一使用字段名 val。

1. 链表与数组

数组支持按下标 O(1) 访问，但在中间插入或删除元素通常要移动后续元素。单向链表按指针逐个访问，查找第 i 个元素需要 O(n)；如果已经拿到待插入位置的前驱节点，插入或摘除节点只需 O(1) 指针修改。

“链表插入删除是 O(1)”有一个前提：必须已经找到位置。若还要先遍历查找，整体仍是 O(n)。链表每个节点还需要额外指针空间，缓存局部性通常不如连续数组。

2. 节点定义

1
2
3
4
5
struct ListNode {
    int val;
    ListNode* next;
    explicit ListNode(int value) : val(value), next(nullptr) {}
};

例如 1 -> 4 -> 7 -> nullptr 表示三个节点依次相连。最后一个节点的 next 是空指针。空链表的头指针为 nullptr。

3. 从数组创建链表

使用虚拟头节点可以避免对空链表和第一个节点做特殊处理。函数返回的是真实头节点；空数组会返回 nullptr。

1
2
3
4
5
6
7
8
9
ListNode* vectorToList(const vector<int>& values) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    for (int value : values) {
        tail->next = new ListNode(value);
        tail = tail->next;
    }
    return dummy.next;
}

这段代码使用 new 分配节点。实际项目中还需要设计对应的释放方式；竞赛平台若提供节点并规定只实现某个函数，应遵循平台的内存管理约定。

4. 删除所有指定值

虚拟头节点让删除头节点也能使用同一套逻辑。删除后当前节点不前进，因为它的新后继也可能需要删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* removeElements(ListNode* head, int target) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* current = &dummy;

    while (current->next != nullptr) {
        if (current->next->val == target) {
            ListNode* removed = current->next;
            current->next = removed->next;
            delete removed;
        } else {
            current = current->next;
        }
    }
    return dummy.next;
}

如果链表节点不归当前函数所有（例如由调用方或判题系统管理），不要擅自 delete；只调整链接并按题目约定处理内存。

5. 反转单向链表

遍历时保存当前节点的后继，再把当前节点的 next 指向前驱。三个指针分别表示前驱、当前节点和尚未处理的后继。

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    ListNode* previous = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* nextNode = current->next;
        current->next = previous;
        previous = current;
        current = nextNode;
    }
    return previous;
}

时间复杂度 O(n)，额外空间复杂度 O(1)。空链表和单节点链表都能正确处理。

6. 判断链表是否为回文

使用快慢指针找到前半部分末尾，反转后半部分，再逐个比较两侧节点。比较结束后把后半部分反转回来，恢复原链表结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ListNode* reverseList(ListNode* head); // 使用上一节的实现

bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return true;

    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* secondHalf = reverseList(slow->next);
    ListNode* left = head;
    ListNode* right = secondHalf;
    bool result = true;
    while (right != nullptr) {
        if (left->val != right->val) {
            result = false;
            break;
        }
        left = left->next;
        right = right->next;
    }
    slow->next = reverseList(secondHalf); // 恢复原链表
    return result;
}

奇数长度链表的中间节点不需要参与两侧比较；偶数长度时，slow 停在前半段的最后一个节点。时间复杂度为 O(n)，额外空间复杂度为 O(1)。

7. 双向链表与循环链表

双向链表的节点另外保存 prev，可以向前和向后遍历；循环链表把尾节点连接回头部。它们适用于需要双向移动或循环遍历的场景，但节点维护更复杂。初学时先掌握单向链表及指针更新，再学习这些变体。

8. 练习