C 语言从入门到实战

Appearance

第 22 讲：数据结构——链表 ​

⏱️ 本讲 L1 内容建议分 3 次 学习：第 1 次吃透单链表与"二级指针"，第 2 次理解带头双向循环链表，第 3 次刷经典 OJ 题。链表是数据结构的第二个核心容器，也是笔试面试的重灾区，务必亲手把每个接口敲一遍。📘 与末尾 🔬 拓展可按需跳过。

🎯 学完本讲，你将能够 ​

  • 解释链表的物理非连续、逻辑连续，以及节点"数据 + 指针"的构成
  • 说清单链表增删接口为什么要传二级指针 SLTNode** pphead
  • 独立实现无头单链表的头/尾插删、查找、任意位置插删、销毁
  • 理解 8 种链表分类，掌握带头双向循环链表"结构复杂但实现统一"的精髓
  • 用快慢指针、双指针等技巧解决反转、合并、找中间结点等经典链表题
  • 根据"读多还是写多"在顺序表与链表之间做出合理选型

🔗 先修知识 ​

指针与解引用（第 12 讲）、结构体自引用（第 14 讲）、malloc/free（第 15 讲）、顺序表（第 21 讲）。

自检三问：

  1. 一个函数想修改调用者传入的指针变量本身，参数应该传什么？
  2. struct Node { int data; struct Node* next; }; 里为什么 next 是指针而不是 struct Node？
  3. 释放一个节点前，为什么常常要先保存它的 next？

一、链表长什么样 ​

链表是一种物理存储上非连续、非顺序的结构，元素之间的逻辑顺序靠指针链接维持。

把它想象成一列火车：每节车厢独立存在，淡季拆几节、旺季加几节，都不影响其它车厢——这正是链表"增删节点不动其它节点"的直观写照。

再想一个问题：如果每节车厢的门都从里面锁死，你只有一把钥匙，怎么从车头走到车尾？最简单的办法——每节车厢里都放一把通往下一节的钥匙。链表节点的 next 指针，就是这把"钥匙"。

每个节点两部分：

c
struct SListNode
{
    int data;                 // 本节点的数据
    struct SListNode* next;   // 下一节点的地址（钥匙）
};

补充三点：① 链式结构逻辑连续、物理不一定连续；② 节点一般从堆上 malloc；③ 堆上每次申请的地址可能连续也可能不连续，靠指针串起来。

二、为什么单链表接口要传二级指针 ​

这是初学者最容易卡住的地方。看头插：

c
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuyNode(x);
    newnode->next = *pphead;   /* 新节点指向旧头 */
    *pphead = newnode;         /* 头指针改指向新节点 */
}

plist 是 main 里的一个指针变量。头插要改变 plist 本身的值（让它指向新节点）。如果形参只传 SLTNode* phead，那只是 plist 的一份拷贝，函数里改 phead 改不到 main 的 plist。要修改"指针变量本身"，就得传它的地址——即二级指针 SLTNode** pphead，函数内通过 *pphead 操作原始指针。

经验法则：凡是可能改变头指针指向的操作（头插、头删、销毁、可能变空的尾删），形参用二级指针；只读取链表（打印、查找）用一级指针。

三、无头单链表的完整实现 ​

📄 01_slist_full.c · ✅ 完整程序（可直接复制编译）

c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
} SLTNode;

/* 统一建节点，判空 */
static SLTNode* BuyNode(SLTDataType x)
{
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); }
    node->data = x;
    node->next = NULL;
    return node;
}

void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur) { printf("%d->", cur->data); cur = cur->next; }
    printf("NULL\n");
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyNode(x);
    if (*pphead == NULL) { *pphead = newnode; return; }
    SLTNode* tail = *pphead;
    while (tail->next) tail = tail->next;
    tail->next = newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; }
    SLTNode* prev = NULL, *tail = *pphead;
    while (tail->next) { prev = tail; tail = tail->next; }
    free(tail);
    prev->next = NULL;
}

void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* cur = phead;
    while (cur) { if (cur->data == x) return cur; cur = cur->next; }
    return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead && pos);
    if (*pphead == pos) { SLTPushFront(pphead, x); return; }
    SLTNode* prev = *pphead;
    while (prev->next != pos) prev = prev->next;
    SLTNode* newnode = BuyNode(x);
    prev->next = newnode;
    newnode->next = pos;
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = BuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    if (*pphead == pos) { SLTPopFront(pphead); return; }
    SLTNode* prev = *pphead;
    while (prev->next != pos) prev = prev->next;
    prev->next = pos->next;
    free(pos);
}

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
}

void SListDestroy(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;
    while (cur) { SLTNode* next = cur->next; free(cur); cur = next; }
    *pphead = NULL;
}

int main(void)
{
    SLTNode* plist = NULL;
    for (int i = 1; i <= 3; i++) SLTPushBack(&plist, i);
    printf("尾插1-3: "); SLTPrint(plist);
    SLTPushFront(&plist, 0);
    printf("头插0:   "); SLTPrint(plist);

    SLTNode* pos = SLTFind(plist, 2);
    SLTInsert(&plist, pos, 99);
    printf("2前插99: "); SLTPrint(plist);
    SLTInsertAfter(pos, 55);
    printf("2后插55: "); SLTPrint(plist);

    pos = SLTFind(plist, 99);
    SLTErase(&plist, pos);
    printf("删99:    "); SLTPrint(plist);

    SListDestroy(&plist);
    printf("销毁后 plist=%p\n", (void*)plist);
    return 0;
}

实测输出：

text
尾插1-3: 1->2->3->NULL
头插0:   0->1->2->3->NULL
2前插99: 0->1->99->2->3->NULL
2后插55: 0->1->99->2->55->3->NULL
删99:    0->1->2->55->3->NULL
销毁后 plist=(nil)

3.1 几个关键细节 ​

  • 销毁必须先存 next 再 free：next = cur->next; free(cur); cur = next;。若先 free(cur) 再取 cur->next，就是访问已释放内存（悬空指针，UB 🔴）。
  • SLTInsertAfter 只需一级指针：它改的是 pos->next（pos 指向节点的成员），不改头指针，所以传 pos 本身即可。对比 SLTInsert（pos 前插）可能要改头，必须二级指针——这个差别正是第二节经验法则的体现。
  • 尾删找前驱：单向链表删尾节点，要先把"倒数第二个"的 next 置 NULL，所以必须遍历找前驱，O(N)。想 O(1) 尾删？用双向链表（见第五节）。
📘 提高（L2）：原课件单链表代码补了两处判空

原课件 BuyNode、SLTInsert、SLTInsertAfter 里 malloc 后没判空就直接用，内存紧张时会解引用空指针崩溃。上面完整程序统一用 BuyNode 封装并判空退出，杜绝这一隐患。养成习惯：每次 malloc 都判空。

四、链表的 8 种分类 ​

三个维度两两组合，共 2×2×2 = 8 种：

维度选项 A选项 B
方向单向（只有 next）双向（next + prev）
带头带头（哨兵节点）不带头（直接第一个数据节点）
循环循环（尾指回头）非循环（尾为 NULL）

实际最常用的两种：

  1. 无头单向非循环链表：结构简单，多作为其它结构的子结构（哈希桶、图的邻接表）；笔试面试高频。
  2. 带头双向循环链表：结构最复杂，但正因如此增删统一、没有特判，工程里单独存数据基本都用它。

五、带头双向循环链表 ​

5.1 哨兵位"phead" ​

注意"带头"的头节点是哨兵位，不存有效数据，只起"放哨"作用，两个价值：

  • 循环链表有了固定参照点，遍历 while (cur != phead) 自然终止，不会死循环；
  • 头插/头删不再特殊——第一个数据节点前永远是哨兵，操作和中间节点完全一致。

5.2 结构与"一个插入打天下" ​

c
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

核心只有两个函数，其余头尾插删全是它们的别名：

c
void LTInsert(LTNode* pos, LTDataType x)   /* pos 之后插入 */
{
    LTNode* newnode = BuyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next->prev = newnode;
    pos->next = newnode;
}
void LTErase(LTNode* pos)                   /* 删除 pos 本身 */
{
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

因为双向 + 循环 + 哨兵，头插、尾插、中间插都用同一个 LTInsert，只是 pos 传谁不同：尾插传 phead->prev、头插传 phead。这就是"结构复杂但实现反而简单"。

📄 02_dlist_full.c · ✅ 完整程序（可直接复制编译）

c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

static LTNode* BuyNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); }
    node->next = node->prev = NULL;
    node->data = x;
    return node;
}

LTNode* LTInit(void)
{
    LTNode* phead = BuyNode(-1);   /* 哨兵位，数据无意义 */
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

void LTPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) { printf("%d<->", cur->data); cur = cur->next; }
    printf("HEAD\n");
}

bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }

void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* newnode = BuyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next->prev = newnode;
    pos->next = newnode;
}

void LTErase(LTNode* pos)
{
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

void LTPushBack(LTNode* phead, LTDataType x)  { assert(phead); LTInsert(phead->prev, x); }
void LTPopBack(LTNode* phead)  { assert(phead && !LTEmpty(phead)); LTErase(phead->prev); }
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
void LTPopFront(LTNode* phead) { assert(phead && !LTEmpty(phead)); LTErase(phead->next); }

LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; }
    return NULL;
}

void LTDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; }
    free(phead);   /* 别忘了释放哨兵位 */
}

int main(void)
{
    LTNode* plist = LTInit();
    for (int i = 1; i <= 3; i++) LTPushBack(plist, i);
    printf("尾插1-3: "); LTPrint(plist);
    LTPushFront(plist, 0);
    printf("头插0:   "); LTPrint(plist);

    LTNode* pos = LTFind(plist, 2);
    LTInsert(pos, 99);
    printf("2后插99: "); LTPrint(plist);

    LTPopBack(plist); LTPopFront(plist);
    printf("头尾各删: "); LTPrint(plist);

    pos = LTFind(plist, 2);
    LTErase(pos);
    printf("删2:     "); LTPrint(plist);
    printf("空? %d\n", LTEmpty(plist));

    LTDestroy(plist);
    return 0;
}

实测输出：

text
尾插1-3: 1<->2<->3<->HEAD
头插0:   0<->1<->2<->3<->HEAD
2后插99: 0<->1<->2<->99<->3<->HEAD
头尾各删: 1<->2<->99<->HEAD
删2:     1<->99<->HEAD
空? 0

双向链表头插/尾插/中间插全部复用 LTInsert，且任意位置插入删除都是 O(1)（给定 pos 的前提下）——这正是它相对单链表的工程优势。

⚠️ 常见坑与报错表 ​

现象原因对策
头插后 main 的 plist 没变形参写成一级指针，改的是拷贝改头指针的操作一律传二级指针
销毁/删除后崩溃先 free(cur) 再读 cur->next先 next = cur->next 保存，再 free
malloc 返回 NULL 后崩溃建节点未判空封装 BuyNode 统一判空退出
单链表尾删丢了倒数第二节忘了找前驱置 NULL遍历到 tail->next==NULL，prev 是前驱
双向链表遍历死循环循环链表用 cur != phead 而非 cur != NULL参照哨兵位判停
双向删除断链只改了一侧指针next/prev 四条链接都要改对
销毁双向链表内存泄漏忘了 free(phead) 哨兵数据节点释放后单独 free 哨兵

🛠️ 动手练习 ​

📊 本讲网页练习进度0 / 8（0%）
进度自动保存在本浏览器；编程题不计数，请在编辑器中完成。

第 1 题（知识点：二级指针 · 难度：⭐⭐）

单链表的头插函数 SLTPushFront，形参为什么是 SLTNode** pphead 而不是 SLTNode* phead？

第 2 题（知识点：销毁顺序 · 难度：⭐⭐）

销毁链表时循环体写成 next = cur->next; free(cur); cur = next;，若改成 free(cur); cur = cur->next; 会怎样？

第 3 题（知识点：插入的指针级别 · 难度：⭐⭐）

SLTInsertAfter（在 pos 之后插入）只需一级指针 SLTNode* pos，而 SLTInsert（在 pos 之前插入）需要二级指针，原因是？

第 4 题（知识点：双向循环遍历 · 难度：⭐）

带头双向循环链表的遍历终止条件通常是？

空①

第 5 题（知识点：链表分类 · 难度：⭐⭐）

关于带头双向循环链表，下列说法正确的有哪些？

第 6 题（知识点：单链表尾删 · 难度：⭐⭐）

无头单链表删除尾节点的时间复杂度是？根本原因是什么？

第 7 题（知识点：反转链表 · 难度：⭐⭐⭐）

🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成

实现 SLTNode* SLTReverse(SLTNode* phead)，反转一个无头单链表并返回新头（LeetCode 206）。

✅ 过关标准：反转后原尾变新头、各 next 指向正确、新尾 next 为 NULL；空表返回 NULL、单节点返回自身；不额外申请节点（原地三指针）。

网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开 思路 → 步骤 → 答案。
💡 思路（卡住再点开）

三个指针 prev=NULL, cur=phead, next。每步：先存 next=cur->next，再把 cur->next=prev（掉头），然后 prev=cur, cur=next 整体后移。cur 到 NULL 时 prev 就是新头。

🔑 点击查看参考答案
c
SLTNode* SLTReverse(SLTNode* phead)
{
    SLTNode* prev = NULL;
    SLTNode* cur = phead;
    while (cur)
    {
        SLTNode* next = cur->next;  /* 先存下一个，防断链 */
        cur->next = prev;           /* 反转指向 */
        prev = cur;                 /* prev 前进 */
        cur = next;                 /* cur 前进 */
    }
    return prev;                     /* prev 停在原尾=新头 */
}

实测：1->2->3 反转为 3->2->1->NULL。

第 8 题（知识点：快慢指针 · 难度：⭐⭐⭐）

🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成

实现 SLTNode* SLTMid(SLTNode* phead)，返回单链表的中间结点；若有两个中间结点，返回第二个（LeetCode 876）。

✅ 过关标准：只遍历一遍（快慢指针）；奇数个返回正中、偶数个返回后半个中间；空表返回 NULL。

网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开 思路 → 步骤 → 答案。
💡 思路（卡住再点开）

快指针每次走 2 步、慢指针每次走 1 步。快到头（快为 NULL 或快的 next 为 NULL）时，慢正好在中间。偶数要返回第二个中间，循环条件用 fast && fast->next。

🔑 点击查看参考答案
c
SLTNode* SLTMid(SLTNode* phead)
{
    SLTNode* slow = phead;
    SLTNode* fast = phead;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

实测：1->2->3->4->5 返回 3；1->2->3->4 返回 3（第二个中间）。

📝 小结与自测 ​

本讲脉络：

  1. 链表物理非连续、靠指针串起逻辑顺序；节点 = 数据 + next（双向再加 prev）。
  2. 无头单链表：改头指针的操作传二级指针，只读的传一级；销毁/删除先存 next 再 free。
  3. 单链表尾删 O(N)（要回溯前驱），这是它相对双向链表的短板。
  4. 8 种分类，工程最常用带头双向循环链表：哨兵统一头尾、LTInsert/LTErase 一招通吃、任意位置增删 O(1)。
  5. 快慢指针、三指针反转是链表题的两大基本功。

自测三问：

  1. 什么时候链表接口用一级指针、什么时候用二级指针？
  2. 带头双向循环链表的"哨兵位"解决了哪两个麻烦？
  3. 顺序表和链表分别适合什么场景？
🔑 自测答案
  1. 操作可能改变头指针指向（头插、头删、销毁、可能变空的尾删、pos 前插）用二级指针；只读取或只改节点成员（打印、查找、pos 后插）用一级指针。
  2. ① 循环遍历有固定终止点 cur != phead，不死循环；② 头插/头删不再特殊，第一个数据节点前恒有哨兵，与中间节点操作一致。
  3. 读多写少、需要按下标随机访问 → 顺序表；任意位置频繁增删、长度变化大 → 链表。

🔬 选学拓展（L3） ​

WARNING

以下为面试高频的链表算法，供准备刷题的同学选学。

拓展 1：合并两个有序链表（LeetCode 21） ​

用哨兵尾指针技巧，避免讨论"新头是谁"：

c
SLTNode* mergeTwoLists(SLTNode* l1, SLTNode* l2)
{
    SLTNode dummy = {0};        /* 栈上哨兵 */
    SLTNode* tail = &dummy;
    while (l1 && l2)
    {
        if (l1->data <= l2->data) { tail->next = l1; l1 = l1->next; }
        else                      { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;  /* 接上剩余 */
    return dummy.next;
}

拓展 2：移除链表元素（LeetCode 203） ​

同样用哨兵简化"删头节点"的特判：

c
SLTNode* removeElements(SLTNode* head, int val)
{
    SLTNode dummy = {0, head};  /* dummy.next = head */
    SLTNode* prev = &dummy;
    while (prev->next)
    {
        SLTNode* cur = prev->next;
        if (cur->data == val) { prev->next = cur->next; free(cur); }
        else prev = cur;
    }
    return dummy.next;
}

拓展 3：约瑟夫环（环形链表） ​

n 个人围一圈，从 1 报数到 m 出列，求最后剩下的人。用循环链表模拟最直观：建 n 个节点首尾相连，每次从当前位置走 m-1 步删一个，直到剩 1 个。此题也有 O(n) 的数学递推解 f(i) = (f(i-1) + m) % i，链表解胜在思路直白、便于理解"循环"结构。

拓展 4：分割链表（LeetCode 86 类） ​

给定值 x，把 < x 的节点放前面、>= x 的放后面，保持相对顺序。技巧是建两条尾插链表（small、large），遍历原链表把节点分别挂上去，最后 small尾 -> large头 拼接。注意收尾把 large 的尾 next 置 NULL。

📜 标准卡（L2 选读）：本讲依据
  • 自引用结构体：C11 §6.7.2.1p6（结构体可含指向自身的指针）。
  • 动态内存与悬空指针：C11 §6.3.2.1p2（访问已释放对象为未定义行为）、§7.22.3（malloc/free）。
  • 栈上对象作哨兵（SLTNode dummy）：C11 §6.2.4（自动存储期），函数返回后 dummy 销毁，但其 next 指向的堆节点仍在，故返回 dummy.next 安全。

内容仅供学习交流，非商业用途。如有侵权请联系删除。

Released under CC BY-NC-SA 4.0 · 基于某 C 语言课件重构