Lesson 0402 · 链表

④ 数据结构与算法 — 第 2 课

1. 链表长什么样

链表里每个元素叫一个节点（Node），节点只存两样东西：

• 数据：val
• 下一个节点的地址：next

struct Node {
    int val;       // 数据
    Node* next;    // 指向下一个节点
};

节点在内存里不要求连续，全靠 next 一个个串起来：

head -> [10|next] -> [20|next] -> [30|nullptr]

最后一个节点的 next 是 nullptr，表示「后面没有了」。整条链表只靠一个 head 指针就能找到全部节点——所以 head 是命根子，一丢，整条链表就找不回来了。

2. 手动搭一条链表

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

int main() {
    Node* a = new Node{10, nullptr};
    Node* b = new Node{20, nullptr};
    Node* c = new Node{30, nullptr};

    a->next = b;      // a 后面接 b
    b->next = c;      // b 后面接 c

    // 现在链表是：10 -> 20 -> 30
    return 0;
}

Node* a 是堆上的一个节点。a->next 等价于 (*a).next，意思是「访问 a 指向的那个节点的 next」。

注意最后一条 b->next = c：三个节点是分别 new 出来的，地址互不相邻也没关系，是 next 把它们连成了一条链。

3. 遍历链表

void printList(Node* head) {
    for (Node* p = head; p != nullptr; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
}

逐行看：

• Node* p = head：从第一个节点开始
• p != nullptr：只要还没走到末尾
• p = p->next：走到下一个节点

循环条件必须是 p != nullptr。如果写成 p->next != nullptr，最后一个节点就不会被访问——这是链表里最常见的差一错误。

4. 头插法：新节点放到最前面

void insertHead(Node*& head, int x) {
    Node* newNode = new Node{x, head};  // 新节点的 next 指向原来的 head
    head = newNode;                     // head 指向新节点
}

注意参数是 Node*& head：我们要修改 main 里的 head 本身，所以要传引用。传值的话改的是副本，函数一返回，main 的 head 还是原来的。

两行的顺序也不能反：先构造新节点、让它接上旧链表，再让 head 指过来。反过来就先丢了旧 head，后面的节点全找不到了。

调用：

Node* head = nullptr;
insertHead(head, 30);
insertHead(head, 20);
insertHead(head, 10);
// 链表：10 -> 20 -> 30

先插 30、再插 20、最后插 10，结果却是 10 20 30——因为每个新节点都抢到了最前面。头插天然会反转插入顺序，这一点下一课还会用到。

5. 在某个节点后面插入

void insertAfter(Node* p, int x) {
    Node* newNode = new Node{x, p->next};
    p->next = newNode;
}

关键步骤：先让新节点接上 p->next，再把 p->next 改成新节点。顺序不能反：如果先把 p->next 改成新节点，原来 p->next 指向的那半条链表就丢了。

6. 删除某个节点后面的节点

void deleteAfter(Node* p) {
    if (p == nullptr || p->next == nullptr) return;  // 后面没有节点

    Node* toDelete = p->next;
    p->next = toDelete->next;      // 跳过 toDelete
    delete toDelete;               // 释放内存
}

删除也只需要改一个指针：让 p->next 跳过要删的节点。不过跳过之前得先用 toDelete 记住它，否则 delete 的时候就没法引用它了。

7. 链表 vs 顺序表

8. 完整示例：头插 + 遍历

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

void insertHead(Node*& head, int x) {
    Node* newNode = new Node{x, head};
    head = newNode;
}

void printList(Node* head) {
    for (Node* p = head; p != nullptr; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
}

int main() {
    Node* head = nullptr;

    insertHead(head, 30);
    insertHead(head, 20);
    insertHead(head, 10);

    printList(head);   // 10 20 30

    return 0;
}

把这段抄进编辑器跑一遍，输出应该是 10 20 30。然后试试把三次 insertHead 的顺序换成 10、20、30，看看输出变成什么——这就是「头插会反转」。

9. 坑点清单

• 头指针丢了：head = head->next 之前没保存旧头，旧头节点就永远回收不了，整条链表也跟着丢。
• 参数没传引用：insertHead(Node* head, int x) 改的是副本，main 里的 head 还是 nullptr。
• 遍历条件写成 p->next != nullptr：最后一个节点会被漏掉。
• 插入顺序反了：先改 p->next 再接新节点，后半条链表当场丢失。
• 删除后还用旧指针：delete 之后那块内存已经不属于你了，再访问就是野指针。
• new 了不 delete：链表用完要逐个释放，否则内存泄漏（下一课第 4 节专门讲）。

10. 小测

11. 动手练习

12. 本课小结

• 节点 = val + next；链表不要求连续内存，靠指针串起来。
• 遍历：for (Node* p = head; p != nullptr; p = p->next)，条件不能写 p->next。
• 头插：新节点 next 指旧 head，再更新 head；顺序会被反转。
• 中间插入/删除：改的是前驱的 next，记得先保存再改。
• 复杂度：链表插删 O(1)，但按下标访问 O(n)；顺序表正好相反。
• 代价：每个节点多存一个指针；链表用完要逐个 delete。