Lesson 0403 · 链表进阶：尾插、查找、删除与释放

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

1. 尾插法：保持输入顺序

头插法会把顺序反过来。尾插法把新节点放到最后，输入和输出顺序就一样了。

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

    if (head == nullptr) {        // 链表是空的：新节点就是头
        head = newNode;
        return;
    }

    Node* p = head;
    while (p->next != nullptr) {   // 走到最后一个节点
        p = p->next;
    }
    p->next = newNode;            // 最后节点接上新节点
}

调用：

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

指针是怎么动的？拿「往 10 → 20 后面接 30」这一趟来看：

尾插唯一容易错的地方是空链表：这时 p = head 就是 nullptr，再去读 p->next 会直接崩。所以循环之前必须先判 head == nullptr。

回看头插：它其实是在反转

头插是「每次把新节点塞到队首」，所以先来的反而被挤到后面。用上节课的例子（依次插入 30、20、10）：

输入 30 20 10，输出 10 20 30：头插就是原地把顺序倒过来。尾插之所以能保持顺序，是因为它每次都老老实实走到队尾，让先来的留在前面。

2. 查找：返回节点地址

Node* find(Node* head, int x) {
    for (Node* p = head; p != nullptr; p = p->next) {
        if (p->val == x) return p;   // 找到就返回这个节点
    }
    return nullptr;                   // 没找到
}

如果返回 nullptr，说明链表中没有这个值。调用方拿到的如果是 nullptr，就不能再写 result->val——先判空再用。

3. 按值删除：删掉所有等于 x 的节点

删除分两步处理：先处理头部连续等于 x 的情况，再处理中间节点。

void deleteValue(Node*& head, int x) {
    // 1. 如果头节点就是要删的值，把头指针后移
    while (head != nullptr && head->val == x) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }

    // 2. 处理中间节点
    Node* p = head;
    while (p != nullptr && p->next != nullptr) {
        if (p->next->val == x) {
            Node* tmp = p->next;
            p->next = tmp->next;      // 跳过 tmp
            delete tmp;
        } else {
            p = p->next;              // 只有没删时才往后走
        }
    }
}

重点：删除成功后 p 不前进，因为新的 p->next 可能还是 x。

拿本课完整示例的链表 10 → 20 → 30 → 20、执行 deleteValue(head, 20)，把「谁指向谁」一步步画出来：

第 2 步是整段代码的灵魂：如果删完立刻 p = p->next，就会跳过后一个 20，最后链表中还剩一个。所以删完必须让 p 留在原地，重新检查新的 p->next。

4. 释放整条链表

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }
}

每次先记住当前节点，头指针后移，再删掉刚记住的节点。顺序是记 → 移 → 删：先 delete head 再读 head->next，读的就是已经释放的内存。最后 head 自动变成 nullptr。

5. 完整示例：尾插 + 查找 + 删除 + 释放

#include <iostream>
using namespace std;

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

// ==== 建表：尾插 ====
void insertTail(Node*& head, int x) {
    Node* newNode = new Node{x, nullptr};
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* p = head;
    while (p->next != nullptr) p = p->next;
    p->next = newNode;
}

// ==== 查找 ====
Node* find(Node* head, int x) {
    for (Node* p = head; p != nullptr; p = p->next) {
        if (p->val == x) return p;
    }
    return nullptr;
}

// ==== 按值删除 ====
void deleteValue(Node*& head, int x) {
    while (head != nullptr && head->val == x) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }

    Node* p = head;
    while (p != nullptr && p->next != nullptr) {
        if (p->next->val == x) {
            Node* tmp = p->next;
            p->next = tmp->next;
            delete tmp;
        } else {
            p = p->next;
        }
    }
}

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

// ==== 释放 ====
void freeList(Node*& head) {
    while (head != nullptr) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }
}

// ==== main ====
int main() {
    Node* head = nullptr;

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

    printList(head);            // 10 20 30 20

    cout << (find(head, 30) != nullptr) << endl;   // 1

    deleteValue(head, 20);
    printList(head);            // 10 30

    freeList(head);
    return 0;
}

6. 坑点清单

• 尾插不判空：空链表时 p = nullptr，再读 p->next 直接崩。代码里的 if (head == nullptr) 不能省。
• 尾插每次都从头走：连续插 n 个数是 O(n²)；想 O(1) 就得维护 tail 指针。
• 删除后让 p 前进了：连续两个相同的 x 只会删掉一个，后面的被跳过。
• 先 delete 再取 next：该先 Node* nxt = tmp->next; 记下来，再释放。
• find 的结果不判空：找不到返回 nullptr，直接 ->val 就是空指针解引用。
• 释放顺序写反：必须「记 → 移 → 删」，顺序错了就是野指针。

7. 小测

8. 动手练习

9. 本课小结

• 尾插法：走到最后，接上新节点，保持输入顺序；空链表要单独处理。
• 查找：遍历比较，找到返回节点，找不到返回 nullptr。
• 删除：先处理头，再处理中间；删除后 p 不动，防止漏删。
• 释放：循环删头节点，顺序是「记 → 移 → 删」，最后 head = nullptr。
• 指针操作的通则：改之前先保存，改完马上在纸上画一遍。