数据结构 —— 链表

什么是链表

链表是线性表的另一种存储方式。与顺序表（数组）不同，链表的每个元素都是独立申请的一块内存（称为节点），通过指针把它们”串”起来。

顺序表：data → [ 1 | 2 | 3 | 4 | 5 ]    内存连续，一格挨着一格

链表：  节点1 → 节点2 → 节点3 → 节点4 → 节点5 → NULL
        [1|●]   [2|●]   [3|●]   [4|●]   [5|●]
        内存是零散的，靠指针(next)把它们连成一条链

两者核心区别：

	顺序表	链表
内存	连续	离散（靠指针相连）
访问	随机访问 O(1)，按下标直接取	只能从头顺序访问 O(n)
插入/删除	O(n)，要移动大量元素	O(1)（改指针即可，前提是已找到位置）
扩容	需要拷贝整个数据区	天然”扩容”，随时 new 一个节点

总结：顺序表适合”查多改少“，链表适合”改多查少“。

---

一、单向链表的结构定义

链式结构的代码套路是固定的：先定义节点结构，再定义表头结构，最后定义操作接口。

1.1 节点结构

linkList.h

typedef int ElemType;

// 定义单链表节点的结构
typedef struct LinkListNode {
    ElemType val;                 // 数据域：存元素
    struct LinkListNode* next;    // 指针域：指向下一个节点
} LinkListNode;

节点 = 数据域 + 指针域。指针域存的是下一个节点的地址，这就是”链”的由来。

注意结构体里的写法是 struct LinkListNode* next 而不是 LinkListNode* next——因为此时 typedef 的名字 LinkListNode 还没有生效，必须用完整的 struct LinkListNode。

1.2 表头结构（含哨兵头节点）

linkList.h

typedef struct {
    LinkListNode header;  // 头节点（哨兵），不存数据，保证操作统一
    int num;              // 存储链表节点的个数
} LinkListHeader;

注意：这里的 header 是一个节点结构体的”实体”（不是指针），它作为哨兵头节点存在。

LinkListHeader (表头)
┌──────────────┐
│ header节点    │     节点1      节点2      节点3
│ val=0,next───┼──→ [1|●] ──→ [2|●] ──→ [3|●] ──→ NULL
│ num=3        │
└──────────────┘

为什么需要这个哨兵头节点？

因为有了它，所有插入删除的代码逻辑完全统一：

• 没有哨兵时：插入到头部要改”头指针本身”，插入到中间要改”某个节点的 next”，两种情况的代码不一样，需要特判
• 有哨兵时：插入位置的前置节点永远是某个节点的 next 字段（头插时前置节点就是哨兵 header），一套代码通吃

这就是”用空间换逻辑统一“的思想，也是 STL 里 list 等容器的常见做法。

---

二、创建与释放

2.1 创建表头

linkList.c - createLinkListHeader

LinkListHeader* createLinkListHeader() {
    // 1. 在堆区申请表头结构体空间
    LinkListHeader* res = (LinkListHeader*)malloc(sizeof(LinkListHeader));
    if (res == NULL) {
        printf("申请表头失败\n");
        return NULL;
    }
    // 2. 初始化：哨兵节点的 next 指向 NULL（空链表），计数为 0
    res->header.next = NULL;
    res->header.val = 0;
    res->num = 0;
    return res;
}

和顺序表一样，表头在堆区申请，返回指针。空链表的状态就是 header.next = NULL。

2.2 释放链表

linkList.c - releaseLinkList

void releaseLinkList(LinkListHeader* linklist_header) {
    if (linklist_header) {
        LinkListNode* p = linklist_header->header.next;  // 从第一个真实节点开始
        LinkListNode* temp;
        // 一路向前：先备份，再前移，最后释放
        while (p) {
            temp = p;
            p = p->next;
            free(temp);
            linklist_header->num--;   // 每释放一个，计数减一
        }
        printf("Release success ! LinkList has %d values\n", linklist_header->num);
        free(linklist_header);        // 最后释放表头
    }
}

释放循环的过程(以第一个节点 A 为例):
① temp = p;                ② p = p->next;            ③ free(temp);
   p ─┐                           p ────┐                  p ────┐
  temp┐                       temp┐                  temp┐
      ▼                           ▼                      ▼
   [A|●] → [B|●] → ...       [A|●] → [B|●] → ...       [A|●] → [B|●] → ...
   temp 指向 A                备份在 temp,A 还没被释放     free(A),下一轮处理 B

先备份 → 前移 → 再释放:顺序永远不能错,否则 p 前移后 A 就"找不到了"

释放的三大要点：

1. 先备份再释放：temp = p; p = p->next; free(temp);——释放 p 之前必须先拿到下一个节点的地址，否则就”断链找不到了”
2. 哨兵节点先不释放：遍历从 header.next 开始，哨兵 header 本身随表头一起释放
3. 释放顺序与创建相反：先释放所有节点，再释放表头

---

三、插入操作

3.1 头插法（insertLinkListHeader）

linkList.c - insertLinkListHeader

int insertLinkListHeader(LinkListHeader* linklist_header, ElemType val) {
    // 1. 创建辅助指针，指向前置节点
    // 头插法的前置节点就是哨兵头节点，天然自带
    LinkListNode* p = &linklist_header->header;

    // 2. 创建新节点，创建之后第一步先初始化
    LinkListNode* new_node = (LinkListNode*)malloc(sizeof(LinkListNode));
    if (new_node == NULL) {
        printf("创建新节点失败\n");
        return -1;
    }
    new_node->val = val;

    // 3. 核心操作：先把新节点接上，再让前置节点跟上
    new_node->next = p->next;   // ① 新节点的 next 指向原来第一个节点
    p->next = new_node;         // ② 前置节点的 next 指向新节点

    // 4. 更新表头计数
    ++linklist_header->num;
    return 0;
}

核心两行，顺序不能反：

① new_node->next = p->next;
              ┌─────────┐
   header ───→│ 原第一个 │────→ 原第二个节点 ──→ ...
              └─────────┘
                   ↑
                   │ next（此刻新节点还"飘"在链外，只是把 next 指了上来）
              ┌─────────┐
              │ 新节点   │
              └─────────┘
   ①先把新节点"挂在"原链上（header 仍然指着原第一个节点，链没断，节点没丢）

② p->next = new_node;
             ┌─────────┐
   header ──→│ 新节点   │──→ 原第一个节点 ──→ ...
             └─────────┘
   ②再让 header 指向新节点，新节点正式"上位"

为什么先①后②？ 如果先写 p->next = new_node，原链就断了——new_node->next = p->next 拿到的将是新节点自己（自环），原节点全部丢失。**”先接新，再改旧”是链表插入的铁律。**

反序执行(先 p->next = new_node,再 new_node->next = p->next)的后果:

① 先执行 p->next = new_node:
   header ──→ 新节点 → ???
   (原第一个节点)        ↑
   原链瞬间断裂,第一个节点没有任何指针指向它 → 永久丢失

② 再执行 new_node->next = p->next:
   此刻 p->next 已经指向新节点自己 → 新节点指向自己(自环)
   header → 新节点 ┐
             ↑     │
             └─────┘
   链表从此只剩这一个节点,其余节点全部丢失

头插法的特点：插入顺序和最终顺序相反。循环头插 1~10，链里是 10 9 8 … 1。

3.2 任意位置插入（insertLinkListPos）

linkList.c - insertLinkListPos

// pos 的取值范围：0 ~ num（pos=num 等价于尾插）
int insertLinkListPos(LinkListHeader* linklist_header, int pos, ElemType val) {
    // 1. 判断位置是否合法
    if (pos < 0 || pos > linklist_header->num) {
        printf("insert pos invalid\n");
        return -1;
    }
    // 2. 创建辅助指针，指向前置节点
    // 头节点位置约定为 -1（哨兵下标）
    LinkListNode* p = &linklist_header->header;
    int index = -1;
    // 当 index 为 pos-1 时，就找到了前置节点
    while (p && (index < pos - 1)) {
        p = p->next;
        index++;
    }
    if (p == NULL) {
        return -1;
    }
    // 3. 创建插入的节点空间，先操作新节点，再操作老节点
    LinkListNode* new_node = (LinkListNode*)malloc(sizeof(LinkListNode));
    if (new_node == NULL) {
        printf("创建新节点失败\n");
        return -1;
    }
    new_node->next = p->next;   // 同头插法，先接新
    p->next = new_node;         // 再改旧
    new_node->val = val;
    linklist_header->num++;
    return 0;
}

找前置节点的核心逻辑：单链表没有”回头路”，要插入到 pos 位置，必须先走到 pos-1 位置（前置节点），再改它的 next。

哨兵(-1) → 节点0 → 节点1 → 节点2 → 节点3 → NULL
           ↑
           p 走到这里 (index = pos-1) 停下

pos=1 时：p 停在节点0（index=0），把新节点插到它后面 = 插到位置1 ✅

插入前后完整对比(向位置 1 插入新节点 X):

插入前:  哨兵(-1) → 节点0 → 节点1 → 节点2 → NULL
                        ↑
                p 停在节点0(前置节点)

插入后:  哨兵(-1) → 节点0 → 新节点X → 节点1 → 节点2 → NULL
                            ↑
                    X 插在节点0 后面 = 位置 1 ✅
                    新节点X 的 next 原本指向节点1,"先接新"接的就是它

• 哨兵下标约定为 -1，第一个真实节点下标为 0，所以前置节点的 index 是 pos-1
• pos 可以等于 num：此时 p 会走到最后一个节点后面（next 为 NULL），插入后即为尾插——这就是 pos 范围写成 0~num 的原因

---

四、删除操作

linkList.c - deleteLinkListVal

int deleteLinkListVal(LinkListHeader* linklist_header, ElemType val) {
    // 1. 创建辅助指针，指向前置节点
    // 单链表只能单向走，删除节点也必须站在"前置节点"的位置上
    LinkListNode* p = &linklist_header->header;

    // 写法一：先找再断，直白
    // while (p->next) {
    //     if (p->next->val == val) break;
    //     p = p->next;
    // }
    // 写法二：用 && 短路技巧，更简洁
    while ((p->next) && (p->next->val != val)) {
        p = p->next;
    }

    // 2. 删除——核心思想就是备份
    // while 有两个出口：找到（p->next 非空）或 走到底（p->next 为空），结果不同，需要判断
    if (p->next) {
        LinkListNode* temp = p->next;  // 备份要删的节点
        p->next = temp->next;          // 让前置节点跳过它
        free(temp);                    // 释放
        linklist_header->num--;
    } else {
        printf("Delete failed! No %d element\n", val);
        return -1;
    }
    return 0;
}

三个关键点：

1. 单链表删除为什么必须找”前置节点”？ 因为删除 = 让前一个节点的 next 跳过自己。而单链表只能顺着 next 往后走，无法回头，所以必须停在被删节点的前一个位置。代码里判断的是 p->next->val == val，p 始终站在前置位。
2. 短路写法：while (p->next && p->next->val != val)——p->next 为 NULL（走到尾）时直接短路退出，不会去解引用 NULL。
3. 备份思想：temp = p->next 把要删的节点备份下来，改链之后再 free(temp)。释放前必须先摘链，防止悬空。

删除前：  header → 节点A → 节点B → 节点C → NULL
                              ↑
                     p 停在这里（p->next 是 B）

删除后：  header → 节点A ──────→ 节点C → NULL
                              (B 被跳过、释放)

---

五、没有头节点怎么办：dummy 虚拟头节点

上面所有操作之所以统一，全靠哨兵头节点。但**刷题时（LeetCode 等）链表往往只有一个头指针 head**，直接指向第一个真实节点，没有哨兵：

struct ListNode {
    int val;
    struct ListNode* next;
};
// head 指向第一个真实节点；空链表时 head == NULL

没有哨兵时，头插的代码会很别扭。插入的本质是”找到前置节点，把新节点接在它后面”：

• 中间插 / 尾插：有前置节点——链上的真实节点，改它的 p->next 即可
• 头插：没有前置节点——链头前面是空的，没有任何节点的 next 可以接新节点，只能把新节点挂到 head 指针上（head = new_node）

于是头插和其他地方插的写法就不一样了，代码必须先判断是不是插到头部：

if (pos == 0) {              // 头插：改 head 指针本身
    new_node->next = head;
    head = new_node;         // head 被重新赋值
} else {                     // 中间/尾插：改节点的 next
    p->next = new_node;
}

（没有 dummy 时，头插改的是 head 本身，所以这类函数通常直接 return head; 把新链头带回给调用方；有了 dummy 后，返回值统一变成 return dummy.next;。）

解决办法：创建一个 dummy 虚拟头节点，让 head 变成”dummy 的 next 字段”——从此头插的前置节点就是 &dummy，和中间插用同一套 p->next 逻辑，不用再特判：

struct ListNode dummy;   // 栈上的临时节点，冒充"哨兵头节点"
dummy.next = head;       // head 挂到 dummy 身后，成为 dummy 的 next 字段

// 找前置节点：p 从 &dummy 出发，和带头节点版完全一样
struct ListNode* p = &dummy;
int index = -1;
while (p->next && index < pos - 1) {
    p = p->next;
    index++;
}
new_node->next = p->next;   // 先接新
p->next = new_node;         // 再改旧（头插时 p 就是 &dummy，同样适用）

return dummy.next;          // 新链头（头插可能改变了 head）

dummy 技巧的本质：头插本来”没有前置节点”，在栈上造一个 dummy 节点后，dummy 就成了链头的前置节点（head 变成 dummy 的 next 字段），头插、中间插、尾插就此统一。函数结束 dummy 自动销毁，新链头由 return dummy.next 带出去。

头插 5 到空链表：
dummy ──→ NULL        →  插入后：
dummy ──→ [5|NULL]  ，return dummy.next = 节点5 ✅

再头插 4：
dummy ──→ [4|●] ──→ [5|NULL] ，return dummy.next = 节点4 ✅

两种方案的取舍：

方案	优点	缺点
哨兵头节点（常驻）	逻辑统一、结构清晰	多一个节点开销
dummy 虚拟头节点（临时）	不占常驻内存	函数结尾要返回/同步新链头

刷题时（LeetCode 等）没有哨兵头节点，dummy 技巧是最常用的解题手段，务必掌握。

---

六、单向循环链表：尾指针的妙用

循环链表 = 把最后一个节点的 next 指回开头，形成闭环。**配合尾指针 rear，尾插可以做到 O(1)**——这是它比普通链表强的地方。（对应代码：03_LinkLoop）

linkLoop.h

typedef struct linkloopNode {  // 节点结构
    ElemType val;
    struct linkloopNode* next;
} LinkLoopNode;

typedef struct {               // 表头结构
    LinkLoopNode header;       // 头节点（哨兵）
    LinkLoopNode* rear;        // 尾指针：指向最后一个节点
    int num;
} LinkLoopHeader;

6.1 初始化

linkLoop.c - initLinkLoopList

// 初始化已经存在的空间（栈上的表头，用 init 而非 create）
void initLinkLoopList(LinkLoopHeader* linkloop_header) {
    linkloop_header->num = 0;
    // 尾指针和头节点的 next 都指向头节点自身
    linkloop_header->rear = linkloop_header->header.next = &linkloop_header->header;
}

空循环链表的标志：header.next == &header（自己指向自己），这是循环链表”空表”和”遍历结束”的统一判断条件。初始化时 rear 也指向自身——因为空表只有一个节点（哨兵），它既是头又是尾。

空循环链表的形态(只有哨兵一个节点):

            ┌───────────┐
            │           │
            ▼           │
        header(哨兵) ────┘
        next == &header,rear 也指向自己

遍历时从 header.next 出发绕一圈,再次回到 header 就是遍历完一圈(停)

6.2 尾插法（O(1) 的关键）

linkLoop.c - insertLinkLoopRear

int insertLinkLoopRear(LinkLoopHeader* linkloop_header, ElemType val) {
    LinkLoopNode* new_node = (LinkLoopNode*)malloc(sizeof(LinkLoopNode));
    if (new_node == NULL) {
        printf("创建新节点失败\n");
        return -1;
    }
    new_node->val = val;
    new_node->next = linkloop_header->rear->next;   // ① 新节点接在"尾的后面"（即头节点）
    linkloop_header->rear->next = new_node;         // ② 尾节点的 next 指向新节点
    // 无论是否存在节点，尾插法尾指针都要更新
    linkloop_header->rear = new_node;               // ③ 新节点成为新尾
    ++linkloop_header->num;
    return 0;
}

普通链表尾插要遍历到尾部（O(n)）；循环链表有 rear 直接知道尾在哪，三步完成：

① 新节点 next 指向"尾的 next"（哨兵头）→ 形成闭环
② 尾的 next 指向新节点 → 接上
③ rear 移到新节点 → 新尾就位

header(哨兵) → 节点1 → 节点2 → 节点3(rear) ──┐
     ↑                                        │
     └────────────── 新节点(新rear) ←──────────┘

记住：循环链表尾插永远三步——接环、接入、更新 rear，和元素个数无关。

6.3 头插法的特殊处理

linkLoop.c - insertLinkLoopHeader

int insertLinkLoopHeader(LinkLoopHeader* linkloop_header, ElemType val) {
    LinkLoopNode* new_node = (LinkLoopNode*)malloc(sizeof(LinkLoopNode));
    if (new_node == NULL) {
        printf("创建新节点失败\n");
        return -1;
    }
    new_node->val = val;
    new_node->next = linkloop_header->header.next;   // 插到哨兵后面
    linkloop_header->header.next = new_node;
    linkloop_header->num++;
    // 头插法一般不会改变尾节点，除非是创建第一个节点的时候
    if (linkloop_header->rear == &linkloop_header->header) {
        linkloop_header->rear = new_node;   // 空表插入第一个节点，尾也要更新
    }
    return 0;
}

头插通常只动哨兵后面，rear 一直指向尾部，不变。唯一例外：还没有尾部的时候，即空链表头插第一个节点——此时这个节点既是头也是尾，必须顺手更新 rear。这就是”创建第一个节点时，头尾指针一起指它“的经典处理。

空表头插第一个节点 X 的前后:

插入前(空环):           header(哨兵) ⇄ 自己
                        rear = &header

插入后:                 header → 节点X ──┐
                            ↑            │
                            └────────────┘
                        节点X 既是第一个节点也是最后一个节点
                        rear 必须从 header 更新为 节点X ✅

6.4 遍历与释放

linkLoop.c - showLinkLoop / releaseLinkLoop

void showLinkLoop(LinkLoopHeader* linkloop_header) {
    LinkLoopNode* p = linkloop_header->header.next;
    while (p != &linkloop_header->header) {   // 回到哨兵 = 遍历完一圈
        printf("%d\t", p->val);
        p = p->next;
    }
    printf("\n");
}

void releaseLinkLoop(LinkLoopHeader* linkloop_header) {
    LinkLoopNode* p = linkloop_header->header.next;
    while (p != &linkloop_header->header) {
        LinkLoopNode* temp = p;
        p = p->next;
        free(temp);
        --linkloop_header->num;
    }
    // 释放完后恢复初始状态
    linkloop_header->rear = linkloop_header->header.next = &linkloop_header->header;
}

循环链表的遍历/释放终止条件从”p != NULL“变成了”p != &header“——因为最后一个节点的 next 指向的是哨兵头而不是 NULL。不能再用 NULL 判断，否则死循环。

---

七、双向循环链表：addNode / delNode 四指针

双向 = 每个节点多一个 prev 指针，可以往前走了。代码上最大的进步是：把”接缝”和”拆缝”封装成两个通用函数，头插尾插删除全部复用。（对应代码：04_DoubleLinkLoop）

doublelinkloop.h

typedef struct doublenode {
    ElemType val;
    struct doublenode* next;   // 后继
    struct doublenode* prev;   // 前驱
} DoubleNode, DoubleHeader;    // 同一个结构体既是节点也是表头（哨兵模式）

注意这里的精巧设计：DoubleHeader 和 DoubleNode 是同一个结构体——表头本身就是一个哨兵节点实体。这是双向循环链表最常见的实现（STL 的 list 就是这个结构）。

┌───────────────────────── 环 ─────────────────────────┐
│                                                        │
▼                                                        │
header(哨兵) ↔ 节点1 ↔ 节点2 ↔ 节点3 ↔ ... ↔ 节点n ──────┘
  next=节点1    prev=header

7.1 初始化

doublelinkloop.c - initDLink

void initDLink(DoubleHeader* double_header) {
    double_header->next = double_header->prev = double_header;  // 自己指自己
    double_header->val = 0;   // 顺手当计数用
}

空双向循环表：next == prev == 自身——整个表就一个哨兵节点。

7.2 核心：addNode（把新节点插到 [prev, next] 之间）

doublelinkloop.c - addNode

static void addNode(DoubleNode* new_node, DoubleNode* next, DoubleNode* prev) {
    new_node->next = next;   // ① 新节点后继
    next->prev = new_node;   // ② 后继的前驱 = 新节点
    new_node->prev = prev;   // ③ 新节点前驱
    prev->next = new_node;   // ④ 前驱的后继 = 新节点
}

四根指针，两根线。画图理解：

插入前：  prev ↔ next
插入后：  prev ↔ new_node ↔ next

new_node->next = next;   → 新节点连后继   ┐
next->prev = new_node;   → 后继连新节点   ┤  左边这条线（new ↔ next）接通
new_node->prev = prev;   → 新节点连前驱   ┤
prev->next = new_node;   → 前驱连新节点   ┘  右边这条线（prev ↔ new）接通

四步的顺序其实没有严格要求（互不覆盖），但保持”先接新节点，再改老节点”的习惯最不容易出错。static 修饰表示它是文件内部工具函数，不对外暴露。

7.3 头插 / 尾插 / 删除，全是 addNode / delNode 的调用

doublelinkloop.c - insertDHeader / insertDRear / delDLink

// 头插：插到哨兵和原第一个节点之间
void insertDHeader(DoubleHeader* double_header, ElemType val) {
    DoubleNode* new_node = (DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->val = val;
    addNode(new_node, double_header->next, double_header);  // 前驱=header，后继=原第一个
    ++double_header->val;
}

// 尾插：插到原尾节点和哨兵之间
void insertDRear(DoubleHeader* double_header, ElemType val) {
    DoubleNode* new_node = (DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->val = val;
    addNode(new_node, double_header, double_header->prev);  // 前驱=原尾，后继=header
    ++double_header->val;
}

// 删除：找到节点后，把它前后两个节点直接"焊"起来
void delDLink(DoubleHeader* double_header, ElemType val) {
    DoubleNode* p = double_header->next;
    for (; p != double_header; p = p->next) {   // 遍历找值
        if (p->val == val) break;
    }
    if (p == double_header) {   // 走到哨兵 = 没找到
        printf("no %d element\n", val);
        return;
    }
    delNode(p->prev, p->next);  // 摘链：前驱的 next 跨过 p 直连后继
    free(p);
    --double_header->val;
}

// delNode：拆缝只做一件事——前驱的 next 指向后继，后继的 prev 指回前驱
static void delNode(DoubleNode* prev, DoubleNode* next) {
    prev->next = next;
    next->prev = prev;
}

delNode 摘链前后(删除节点 B):

删除前:    header ↔ A ↔ B ↔ C ↔ ...(环回 header)
                        ↑
               p 停在 B(找到了要删的节点)

delNode(B->prev, B->next) = delNode(A, C):
   prev->next = C   → A 的 next 直连 C
   C->prev = A      → C 的 prev 直连 A

删除后:    header ↔ A ──────↔ C ↔ ...(环回 header)
                B 已被摘出、free,整环依旧闭合

双向链表的三大优势：

1. 删除 O(1)：单链表删除必须找前置节点，双向链表 p->prev 直接就是前置，摘链只要两行（prev->next = next; next->prev = prev）
2. 头插尾插完全对称：头插是 (header, header->next)，尾插是 (header->prev, header)，一套 addNode 通吃，没有任何特判
3. 哨兵模式天然闭环：不需要维护 head/tail 两个指针，头尾操作都退化成”在哨兵身边插/删”

---

八、实战应用：约瑟夫环问题

约瑟夫问题（约瑟夫环）：n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出列，下一个人重新从 1 报数，直到剩最后一个人。经典应用，天然适合用循环链表模拟。

8.1 问题建模

Joseph.h

typedef struct josephnode {
    int val;
    struct josephnode* next;
} JosephNode;

// 约瑟夫环的表头，只保留头尾指针
typedef struct {
    JosephNode* head;   // 头指针
    JosephNode* tail;   // 尾指针
} JosephHeader;

注意这里没有哨兵节点，只有头尾两个指针——因为约瑟夫环要频繁”转圈报数”，头尾指针直接定位最方便。它依然是循环链表（tail->next == head）。

约瑟夫环的内存形态(head/tail 双指针 + 永远闭环):

JosephHeader
┌──────────────────┐
│ head ──┼──→ 1 → 2 → 3 → ... → n ──┐
│ tail ──┼───────────────────────────┘
└──────────────────┘
               tail->next == head,环永远闭合

8.2 初始化：尾插建环 + 首尾相接

Joseph.c - initJosephGame

void initJosephGame(JosephHeader* joseph_header, int n) {
    for (int i = 1; i <= n; i++) {
        JosephNode* new_node = (JosephNode*)malloc(sizeof(JosephNode));
        if (new_node == NULL) {
            printf("创建新节点失败\n");
            return;
        }
        new_node->val = i;
        new_node->next = NULL;
        // 判断是否是空链表
        if (joseph_header->head == NULL) {
            // 第一个节点：头尾指针同时指向它
            joseph_header->head = joseph_header->tail = new_node;
        } else {
            // 后续节点：只需更新尾指针
            joseph_header->tail->next = new_node;
            joseph_header->tail = new_node;
        }
        joseph_header->tail->next = joseph_header->head;   // 每次插入后都重新闭环
    }
}

空表的首节点头尾指针相同，后续节点只动尾指针，最后闭环——没有哨兵时建循环链表的固定套路。每次插入末尾都执行 tail->next = head，保证环永远闭合。

建环三步(以 1、2 两个节点为例):

① 空表:               head = tail = NULL

② 插入节点1:          head = tail = 节点1,首尾同指
                      ┌───────┐
                      │       ▼
                      1 ──────┘

③ 插入节点2:          tail->next = 节点2;tail = 节点2;闭环
                      ┌─────────┐
                      │         ▼
                      1 → 2 ────┘

8.3 遍历：do-while 的用武之地

Joseph.c - showData

void showData(JosephHeader* joseph_header) {
    JosephNode* p = joseph_header->head;
    // 没有头节点，只有头指针的循环链表的遍历方式——do while 循环
    do {
        printf("%d\t", p->val);
        p = p->next;
        // 先执行一次，然后再判断是否回到起点
    } while (p != joseph_header->head);
    printf("\n");
}

普通循环链表有哨兵，用 while (p != &header)；**无哨兵的循环链表必须用 do-while**——因为第一次进来 p 就是合法节点，判断放在后面才能完整走完一圈再停。

8.4 核心：淘汰逻辑（pre / cur 双指针）

Joseph.c - startJosephGame

void startJosephGame(JosephHeader* joseph_header, int m) {
    JosephNode* pre = NULL;                    // 前驱：淘汰时用它摘链
    JosephNode* cur = joseph_header->head;     // 当前指针：从第一个人开始报数
    while (cur->next != cur) {                 // 环上只剩一个节点时结束
        for (int i = 1; i < m; i++) {          // 报数 m-1 次，cur 停在"报到 m"的人上
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;                 // 摘链：前驱跳过 cur
        printf("%d号淘汰\t", cur->val);
        free(cur);                             // 释放
        cur = pre->next;                       // 下一个人从 1 重新报数
    }
    printf("最后剩下的是%d号\n", cur->val);
}

淘汰一个节点的全过程(以 m=3 为例,cur 从 1 出发报到 3):

① 报数(m-1 步):       ② 摘链:                  ③ 换人:
   pre=2  cur=3           pre->next = cur->next     cur = pre->next
   1 → 2 → 3 → 4 ...     1 → 2 ────→ 4 ...         从 4 开始重新报 1
        ↑    ↑                3 被摘出、free        1 → 2 → 4 → 5 ...
       pre  cur

逐行拆解：

1. 为什么报 m 次只走 m-1 步？ 因为 cur 初始已经站在第 1 个人上，for (i=1; i<m; i++) 再走 m-1 步正好停在报到 m 的人身上
2. 为什么需要 pre？ 这是无哨兵的单向链表，删除仍然要找前置节点——pre 就是干这个的
3. 淘汰三步：pre->next = cur->next（摘链）→ free(cur)（释放）→ cur = pre->next（从下一个人重新开始报数）
4. **终止条件 cur->next != cur**：环上只剩一个节点时，它自己指向自己——这是”单节点环”的标志，跳出后它即幸存者

8.5 运行模拟（n=10，m=3）

初始：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → (回1)

第1轮：从1报数，3号淘汰 → 剩余 1 2 4 5 6 7 8 9 10
第2轮：从4报数，6号淘汰 → 剩余 1 2 4 5 7 8 9 10
第3轮：从7报数，9号淘汰 → 剩余 1 2 4 5 7 8 10
第4轮：从10报数，2号淘汰 → 剩余 1 4 5 7 8 10
第5轮：从4报数，7号淘汰 → 剩余 1 4 5 8 10
第6轮：从8报数，1号淘汰 → 剩余 4 5 8 10
第7轮：从4报数，8号淘汰 → 剩余 4 5 10
第8轮：从10报数，5号淘汰 → 剩余 4 10
第9轮：从10报数，10号淘汰 → 剩余 4

输出：3号淘汰 6号淘汰 9号淘汰 2号淘汰 7号淘汰 1号淘汰 8号淘汰 5号淘汰 10号淘汰
最后剩下的是4号 ✅

---

九、复习要点总结

9.1 四版链表代码对照

版本	表头结构	空表标志	遍历终止	亮点
单向链表（带头节点）	哨兵 header + num	header.next == NULL	p != NULL	插入删除逻辑统一
单向链表（无头节点）	头指针 next	next == NULL	p != NULL	dummy 虚拟头节点技巧
单向循环链表	哨兵 + 尾指针 rear	next == &header	p != &header	尾插 O(1)
双向循环链表	哨兵即表头	next == prev == &header	p != &header	addNode/delNode 通用

9.2 操作复杂度

操作	单链表（带头）	循环链表（带 rear）	双向循环链表
头插	O(1)	O(1)	O(1)
尾插	O(n)（要遍历）	O(1)	O(1)
任意位置插入	O(n)	O(n)	O(n)
按值删除	O(n)（找前置）	O(n)	O(n)，但找到后摘链 O(1)
查找	O(n)	O(n)	O(n)

9.3 面试常问细节

1. 为什么要哨兵头节点？ — 让头插和中间插共用”前置节点”逻辑，删除也无需特判”删的是不是第一个”，代码统一、不易出错
2. 单链表删除为什么必须找前置节点？ — 单向链表只能顺着 next 走，删除的本质是”前一个节点跳过自己”，而前一个节点无法回头访问，只能先走到它
3. 插入时”先接新、再改旧”为什么不能反？ — 先改旧会让原链断开，新节点无法挂接，后续节点全部丢失
4. 循环链表如何判断空表和遍历结束？ — 统一用 p == &header（有哨兵）或 p == head（无哨兵），永远不能用 NULL
5. 为什么循环链表尾插能 O(1)？ — 尾指针 rear 直接定位尾节点，免去 O(n) 的找尾遍历
6. 双向循环链表删除为什么更优？ — 节点自带 prev，前置节点 O(1) 可得，摘链只需 delNode(p->prev, p->next) 两行
7. dummy 虚拟头节点什么时候用？ — 刷题时链表常常只有头指针，局部创建 dummy 即可复用统一的插入逻辑，无需特判头插；函数结尾 return dummy.next 带出新链头（仓库里 02_2ChainList 则是把新链头同步回表头的 header->next）
8. 为什么要有 ElemType？ — 数据结构只关心”组织方式”不关心”元素类型”，typedef 一次，换类型只改一行

---