Olverae Assets

1 一句话定义

链表（linked list）就是一串「节点」，每个节点装一个值 + 一根指向下一个节点的指针，靠指针一个接一个串起来，最后一个指向 NULL 表示结束。

把它想成一列火车：每节车厢（节点）装着货物（值），还挂着一个钩子（next 指针）勾住下一节车厢。你只攥着车头（head），想找第 5 节就得从车头一节节数过去——这就是链表"不能随机跳转、只能顺着走"的特点。好处是插入/删除只要改钩子，不像数组那样要整体搬家。

每个方块是一个节点：左格装值、右格是指向下一个的指针。head 攥着第一个节点，顺着箭头能走到底，最后一个指向 NULL。下一节你将亲手"头插"新节点，看指针怎么重新接线。

2 模型 · 头插法：看指针怎么重新接线

链表所有操作的本质都是改指针。这里演示最常见、也最容易写错的「头插」——在链表最前面插入一个新节点，关键是两步指针操作的顺序。

节点怎么定义、链表怎么头插

一个节点 = 一个值 + 一根 next 指针。头插就两行，但顺序不能反。

// 节点：装一个值 + 指向下一个节点的指针
struct node { int value; struct node *next; };

// 造一个新节点
struct node *newNode(int v) {
    struct node *n = malloc(sizeof(struct node));
    n->value = v; n->next = NULL;
    return n;
}

// 头插：在最前面插入 v（注意两步的顺序！）
struct node *insertHead(struct node *head, int v) {
    struct node *n = newNode(v);
    n->next = head;     // ① 先让新节点接住旧链头
    head = n;           // ② head 指向新节点（它成了新链头）
    return head;        // 返回新链头给调用方（head 是按值传入的，必须 return）
}

顺序是命根子：必须先 n->next = head（让新节点记住旧链头），再把 head 换成新节点。反过来先丢了 head，旧链就再也找不到了（断链 + 内存泄漏）。下面点 ▶ 一步步看这两步。

头插法演示 · 依次插入 30、20、10

代码（当前行高亮）

提示

点 ▶ 演示头插：每次插入分两步——先 new->next = head（蓝箭头接住旧链头），再 head = new（紫指针移到新节点）。

3 核心要点 · 4 句人话吃透链表

每张卡片先一句大白话。重点：链表 vs 数组的取舍，以及"遍历到 NULL 为止"这个铁律。

① 链表 vs 数组

一句话：数组能随机跳转(a[5] 一步到位)但插删要搬家；链表插删只改指针，但找第 k 个得从头走。

数组：取第 k 个 O(1)，中间插入/删除 O(n)（要挪后面所有元素）。链表：头部插入/删除 O(1)，但访问第 k 个 O(n)（只能顺着 next 数过去）。各有所长。

② 遍历：cur 走到 NULL 为止

一句话：用一个移动指针 cur，从 head 出发，每次 cur = cur->next，直到 cur == NULL。

这是链表最核心的循环骨架。条件必须是 cur != NULL（不是 cur->next != NULL，那会漏掉最后一个节点）。

for (cur = head; cur != NULL; cur = cur->next) sum += cur->value; // 处理每个节点

③ 改指针的顺序很关键

一句话：插入/删除时，先接住"还要用的那一头"，再断开，否则链就丢了。

头插要先 new->next = head 再移 head；删除节点要先用一个 prev 记住前驱、接好 prev->next = cur->next，再 free(cur)。顺序反了就断链或泄漏。

④ 链表天生适合递归

一句话：一个链表 = 头节点 + 剩下的链表，和"剩下的"又是链表——所以求和、求长、反转都能递归写。

基准是空链 head == NULL。如 sum(head) = head==NULL ? 0 : head->value + sum(head->next)。2521 真题就考过"禁用循环、只能递归"处理链表。

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是写链表最常翻车的坑——头插顺序反了断链、遍历漏判 NULL、删除忘 free、对空链直接解引用。点击卡片看运行效果。

① 头插顺序反了

先 head=new 再 new->next=head → 旧链丢失

② 对空链/越界解引用

head 为 NULL 还访问 head->value → 段错误

③ 遍历条件写错

用 cur->next != NULL → 漏掉最后一个节点

④ 删除忘了 free / 断链

直接跳过节点没 free → 内存泄漏

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对链表套路：节点结构、头插顺序、遍历条件、与数组的取舍、递归处理。最后到练习系统亲手建链表、遍历。

去做例题：链表 · 建表并打印

去做例题