# 指针之舞：单链表三大经典问题的工程化解构

单链表是数据结构领域的指针训练场。合并有序链表考察**归并思想与哑节点运用**，分割链表训练**原地重连与虚拟头技巧**，约瑟夫问题则深入**环形结构的循环删除**。三道题目覆盖了单链表操作的核心场景：有序合并、条件拆分、循环删除。本文从工程化视角出发，以C语言为载体，逐一拆解其指针操作模式与边界防护策略。

---

## 一、合并两个有序链表：哑节点的归并范式

**问题语义**：输入两个升序单链表，返回合并后的升序链表。

**核心洞察**：归并排序的合并阶段可直接迁移至链表结构。与数组不同，链表合并**无需额外存储空间**，仅通过调整`next`指针完成结点重组。

**哑节点策略**：为规避对`head`是否为空的重复判断，引入**哑节点**作为新链表的虚拟头结点。此技巧使循环逻辑统一为`tail->next = min_node`，无需区分首结点。

```c

typedef struct Node {

int val;

struct Node* next;

} Node;

Node* mergeTwoLists(Node* l1, Node* l2) {

Node dummy = {0, NULL}; // 栈上分配哑节点，无需释放

Node* tail = &dummy;

while (l1 && l2) {

if (l1->val < l2->val) {

tail->next = l1;

l1 = l1->next;

} else {

tail->next = l2;

l2 = l2->next;

}

tail = tail->next;

}

// 剩余结点直接挂接

tail->next = l1 ? l1 : l2;

return dummy.next;

}

```

**工程要点**：

- 哑节点若在堆区分配，务必在函数返回前释放，否则造成内存泄漏；

- 剩余结点挂接**无需循环遍历**，链表连续性使单次赋值生效。

**递归版本**虽代码简洁（`l1->next = mergeTwoLists(l1->next, l2)`），但**函数调用栈深度与链表长度线性相关**，长度过万时存在栈溢出风险。迭代版本无此隐患。

---

## 二、分割链表：双虚拟头的原位重组

**问题语义**：给定链表与阈值`x`，将所有小于`x`的结点置于大于等于`x`的结点之前，**保持两部分内结点原始相对顺序**。

**核心难点**：不允许开辟新链表结点，需**原地重连**；且需同时维护两条子链的尾指针。

**双虚拟头解法**：创建两个哑节点，分别作为“小于链”与“大于等于链”的虚拟头。一次遍历，根据当前结点值与`x`的关系，将其挂载至对应链尾。遍历结束后，将两条子链首尾相接。

```c

Node* partition(Node* head, int x) {

Node small_dummy = {0, NULL};

Node large_dummy = {0, NULL};

Node* small_tail = &small_dummy;

Node* large_tail = &large_dummy;

<"z4.a8k1.org.cn"><"j6.a8k1.org.cn"><"n3.a8k1.org.cn">

Node* cur = head;

while (cur) {

Node* next = cur->next; // 预先保存，防止指针丢失

cur->next = NULL; // 剥离当前结点

if (cur->val < x) {

small_tail->next = cur;

small_tail = cur;

} else {

large_tail->next = cur;

large_tail = cur;

}

cur = next;

}

// 连接两段

small_tail->next = large_dummy.next;

return small_dummy.next;

}

```

**陷阱规避**：

- **必须将当前结点`next`置空**，否则原链残留的后继引用会将整个剩余链错误带入子链；

- **预先保存`cur->next`**，因`cur->next`即将被改写。

**时间复杂度**O(n)，**空间复杂度**O(1)，仅使用若干指针变量。

---

## 三、环形链表的约瑟夫问题：循环删除与幸存者

**问题语义**：n个人围成一圈，从第1个开始报数，每数到m的人出列，从下一个人重新报数。求最后幸存者的原始编号。

**数据结构映射**：将编号1~n构建为**单向环形链表**，模拟报数删除过程。

**报数移动逻辑**：删除某结点需访问其**前驱结点**。单链表无`prev`指针，解决方案是**移动`prev`与`cur`双指针同步前进**，或**提前停在待删结点的前驱**——即移动`m-1`步而非`m`步。

```c

int josephus(int n, int m) {

// 1. 构建环形链表（编号1~n）

Node* head = (Node*)malloc(sizeof(Node));

head->val = 1;

Node* prev = head;

for (int i = 2; i <= n; i++) {

Node* node = (Node*)malloc(sizeof(Node));

node->val = i;

prev->next = node;

prev = node;

}

prev->next = head; // 成环

<"w7.a8k1.org.cn"><"g9.a8k1.org.cn"><"q2.a8k1.org.cn">

// 2. 模拟报数

Node* cur = head;

Node* tail = prev; // cur的前驱

int count = 0;

while (cur->next != cur) { // 剩余不止一人

// 报数m-1步，停在待删结点的前驱

for (int i = 1; i < m; i++) {

tail = cur;

cur = cur->next;

}

// 删除cur结点

tail->next = cur->next;

free(cur);

cur = tail->next; // 从下一个开始继续报数

}

int survivor = cur->val;

free(cur);

return survivor;

}

```

**性能瓶颈**：每删除一个结点需移动`m`步，整体时间复杂度O(n×m)。当n达十万级时，**数学解法**（递推公式`f(n,m) = (f(n-1,m)+m)%n`）可将复杂度降至O(n)。但链表模拟**胜在直观与工程可验证性**。

**注意**：

- 环形链表**无空指针**，循环终止条件为`cur->next == cur`；

- 释放结点时**先取后继，再释放当前**，避免野指针访问。

---

## 四、三种操作的共性思维

三题表面上差异显著，内里却共享同一套指针操作哲学：

|--------------|------------------|----------------------|----------------|

**哑节点**消除头结点特判，**预存后继`next`**保障指针安全，**结点剥离先断后接**——这三条原则可迁移至绝大多数单链表操作。

单链表的指针操作是嵌入式驱动开发、操作系统内核链表模块的基础能力。合并两链是归并排序的前置步骤，分割链表是快排划分的链表版本，约瑟夫问题则是循环队列的极端变体。理解此三题，并非为了应对笔试，而是建立对**结点生命周期、指针时序、边界条件**的系统敏感度。