这一章在干嘛？
把结构 + 指针 + 动态内存三者合体，实现真正的数据结构：单链表的有序插入（重点）、双链表，以及「指向 link 字段的指针」这一教科书级技巧。
12.1 单链表与有序插入
typedef struct Node {
int value;
struct Node *next;
} Node;
在有序链表中插入 value，要找到「最后一个小于 value 的节点」，新节点插在它后面。朴素写法要为「插在表头」单独写分支，因为改的是根指针本身；更漂亮的做法是用「指向 link 字段的指针」当游标：
/* 返回值：是否插入成功（内存不足失败） */
int sll_insert(Node **rootp, int new_value)
{
Node *cur = *rootp; /* cur：当前 link 字段指向的节点 */
Node *prev = NULL;
while (cur != NULL && cur->value < new_value) {
prev = cur;
cur = cur->next;
}
/* 此时应插在 prev（可能 NULL）之后、cur（可能 NULL）之前 */
Node *fresh = malloc(sizeof *fresh);
if (fresh == NULL)
return 0;
fresh->value = new_value;
if (prev == NULL) { /* 插表头：改根指针 */
fresh->next = *rootp;
*rootp = fresh;
} else { /* 插中间/尾部：改 prev 的 link */
fresh->next = cur;
prev->next = fresh;
}
return 1;
}
/* 调用：sll_insert(&root, 42); —— 传根指针的地址 */
12.2 消灭特例：link-in-node 技巧
上面的 if/else 两个分支本质是同一句话：「让某个 link 字段指向新节点，新节点指向 cur」。表头分支改的是根指针，中间分支改的是某节点的 next——如果游标直接落在「link 字段本身」，两种情况就统一了：
int sll_insert2(Node **rootp, int new_value)
{
Node **linkp = rootp; /* linkp：下一个 link 字段的位置 */
Node *cur;
while ((cur = *linkp) != NULL && cur->value < new_value)
linkp = &cur->next; /* 游标推进到下一个 link 字段 */
Node *fresh = malloc(sizeof *fresh);
if (fresh == NULL)
return 0;
fresh->value = new_value;
fresh->next = cur;
*linkp = fresh; /* 统一写法：改 link 字段，一招通吃 */
return 1;
}
为什么这招妙：
游标类型是 Node**——「指向 link 字段的指针」。表头时它 = &root，中间时它 = &prev->next，对 *linkp 赋值两种情况行为一致。特例消失 = bug 消失。
接线顺序铁律：
先 fresh->next = cur 接「右边」，再 *linkp = fresh 接「左边」。反过来先把 *linkp 指向 fresh，cur 那一半链就丢了。
12.3 双链表：删除 O(1) 的代价
单链表删除某节点需要先找到前驱（O(n)）；双链表每个节点带 prev 指针，拿到节点就能自删。代价是多一个指针的存储和维护：
typedef struct DNode {
int value;
struct DNode *fwd; /* 向后 */
struct DNode *bwd; /* 向前 */
} DNode;
int dll_insert(DNode **rootp, int new_value)
{
DNode **fwdp = rootp, *bwd = NULL, *cur;
while ((cur = *fwdp) != NULL && cur->value < new_value) {
bwd = cur;
fwdp = &cur->fwd;
}
if (cur != NULL && cur->value == new_value)
return 1; /* 已存在 */
DNode *fresh = malloc(sizeof *fresh);
if (fresh == NULL)
return 0;
fresh->value = new_value;
fresh->fwd = cur; /* 右接 */
*fwdp = fresh; /* 左接（统一 link 技巧） */
fresh->bwd = bwd; /* 反向指针两个方向都要修 */
if (cur != NULL)
cur->bwd = fresh;
return 1;
}
双链表的检查口诀：每个操作后，正向走一遍、反向走一遍，都通才算对。fwd 和 bwd 共 4 处指针（2 组），改漏任何一处链就断。
本章通关标准：
能手推「插入 3 节点链表中间」的每条指针变化；理解 Node** 游标如何统一表头/表内两种插入；记住接线顺序「先右后左」。
1. 单链表插入为什么可能需要修改根指针？什么情况下不用？
插在表头时，根指针本身必须改指向新节点（改的是指针变量，不是节点内容），所以函数要接收 Node**（根指针的地址）。插在中间/尾部只改前驱节点的 next 字段，不需要动根指针。用 link 字段游标（Node**）可把两种情况统一。
2. 链表插入时先接右边还是先接左边？为什么？
先接右边：fresh->next = cur。若先让左边指向 fresh，原来指向 cur 的那条链被覆盖，cur 之后的整段链表就找不到了。先右后左保证任何时刻链不断。
3. 双链表比单链表多付出什么、换来什么？
每个节点多一个 bwd 指针的存储、每次插入/删除要多维护两个方向的指针。换来：拿到任意节点可 O(1) 删除自身、可反向遍历。检查时正反各遍历一遍验证四条指针都改对。