Code59 零基础 · 链表 · 16—27

2026-09-14 · 零基础讲解 · 先读题目与条件，再看示例和逐步讲解

先读 第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。

本篇对应全书第 16—27 题。默认带头结点，头结点不算数据；L->next 才是首个元素。p=q 是让指针指向同一结点，p->next=q 才是改变链的连接。除判环题外默认输入是有效无环链表。题意为转述，例子为本次补充，原代码只读。页码为 Code59 PDF 页序。

返回总目录

读代码前：编译环境与类型

本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAXSIZE 50

以下是本章使用的类型定义，不是要执行的解题步骤。字段含义见第 0 课；不要把不同章节重复的同名类型在同一文件中再定义多次。

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

16｜单链表原地逆置（本章第 1 题）

题目与要求

题目（依据原题整理）：编写算法，将一个带头结点的单链表就地逆置，使原来从前到后的数据结点改为从后到前排列，辅助空间复杂度为 O(1)。

已知条件：L 指向头结点；头结点不存放本题的有效数据，首个数据结点是 L->next，正常链表以 NULL 结束。

需要得到：在保留原头结点和原数据结点的情况下，把链接关系反转，不能另建一份链表代替原链表。

输入 → 输出示例（教学补充）：L→1→2→3→NULL → L→3→2→1→NULL。

约定与提醒（教学补充）：“原地”允许用几个临时指针，不允许按结点数另开数组或新建数据结点。输入链表本身无环；空表和只有一个数据结点的表逆置后不变。

题干回源：Code59 PDF 第 10 页；回源 · PDF 第 10 页 · b_10_1 。

1. 这题先别背“头插”，先认清谁是结点

输入 H→1→2→3→NULL，H 是头结点，1、2、3 是三个不同数据结点。输出要 H→3→2→1→NULL。不换数据、不新建三个结点，而是改三个结点里保存的 next 地址。

L 始终指 H；p 指“还没搬的第一个结点”；next 是临时指针，专门记住后面尚未处理的一串。变量名 next 与结点字段 p->next 不同：前者是临时书签，后者是结点里面那根箭头。

2. 第一轮连每根箭头都展开

先 p=L->next，所以 p 指 1；再 L->next=NULL，把 H 当作空结果链入口，但旧串仍被 p 保存，没有消失。

执行语句	p / next 指向哪里	结果链 H 后面是什么	尚未处理的串
next=p->next	p=1，next=2	空	1→2→3
p->next=L->next	p 仍为 1	空	1 改指 NULL，2→3 由 next 保住
L->next=p	p 仍为 1	H→1→NULL	2→3
p=next	p 改指 2	H→1→NULL	从 p 可读到 2→3

第二轮同四句：先保存 3，让 2 指向目前首结点 1，让 H 指向 2，p 改指 3，结果 H→2→1。第三轮保存 NULL，让 3 指 2、H 指 3，p 变 NULL，结束。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void reverseList(LinkList L) {
    LinkList p = L->next;
    L->next = NULL;

    while (p != NULL) {
        LinkList next = p->next;
        p->next = L->next;
        L->next = p;
        p = next;
    }
}

函数参数 L 是头结点地址，它不需要返回一张新表，因为改的就是原结点箭头。最前两句“存旧入口，再清空新入口”顺序不能交换；若先清空 L->next 再取 p，就只取到 NULL。

while 的条件是还有未处理结点。每轮四句的任务依次是保住后路、当前结点接到结果前面、更新结果入口、移动工作指针。注意 L->next=p 没有移动 p；只有最后 p=next 才让 p 去处理下一个原结点。

4. 自己试：最危险的一句为什么必须先写

若先执行 p->next=L->next 再 next=p->next，读到的是新箭头，不是旧后继，原来 2→3 那串的入口就丢了。练习只含一个数据结点 H→9：先存 p=9、清空 H；next=NULL；9 接 NULL、H 接 9、p=NULL，原样结束。

学懂后回看：结论、复杂度与回源

题意与结论：把 L→1→2→3→NULL 改成 L→3→2→1→NULL，不重新申请数据结点。逐个摘下原链结点，头插到新链即可。

思路推导：数组可两端交换，单链表却不能方便地从尾向前走。头插的特点正是“后来的排到前面”：按 1、2、3 的次序头插，结果天然为 3、2、1。

走一遍：先让 p 保存旧首结点 1，再令 L->next=NULL。取 1：保存其后继 2，头插后新链 [1]；取 2：保存 3，头插后 [2,1]；取 3：保存 NULL，头插后 [3,2,1]，结束。

代码抓手与正确性：每轮按 next=p->next → p->next=L->next → L->next=p → p=next 执行。next 保存通往未处理部分的唯一入口，不能先改 p->next 再去找旧后继。始终维持“新链是已处理前缀的逆序、p 指向未处理后缀”。

复杂度与易错点：时间 O(n)，空间 O(1)。头结点本身不参与逆置，也不能丢失。空链、单结点链都自然成立。原地操作改的是 next，不是输出一串倒序值。

回源：PDF 第 10 页；回源 · PDF 第 10 页 · b_10_1；PDF 第 10 页 · b_10_4 。正式代码

17｜唯一最小结点：奇数交换，偶数删后继（本章第 2 题）

题目与要求

题目（依据原题整理）：在无序正整数单链表中找到唯一的最小值结点。若最小值是奇数，将该结点与它的后继结点交换位置；若是偶数，删除它的后继结点。交换必须通过修改链接实现，不能只交换数值。

已知条件：输入带头结点的非空单链表，最小值只出现一次；“后继”指紧接在该结点后面的结点。

需要得到：完成相应操作后的链表。下面函数成功返回 true；最小结点没有后继时，不改链表并返回 false。

输入 → 输出示例（教学补充）：L→7→3→8→NULL → L→7→8→3→NULL；L→7→2→8→NULL → L→7→2→NULL。

约定与提醒（教学补充）：判断奇偶的是最小结点里的数，不是它的位置；偶数分支删的是后继，不是最小结点本身。数据结点须可按本章约定释放。

题干回源：Code59 PDF 第 10 页；回源 · PDF 第 10 页 · b_10_3 。

1. 题目分两个阶段，别一边找一边删

先找唯一最小值结点，找到之后才根据奇偶进行操作。奇数交换它和后继的结点位置；偶数保留它、删掉后继。输入 H→8→3→6→9，最小为 3，输出 H→8→6→3→9。

要记的不仅是最小结点，还要记它的前驱。minPrev 是最小结点前面那个结点，minNode=minPrev->next 是最小结点，successor=minNode->next 是后继。例子分别是 8、3、6。

2. 找最小值，然后改三根箭头

扫描时 p 从 H 开始，比较的是 p 后面那个结点：先看 8，初始候选也为 8；再 p 指 8 时看 3，3 更小，所以 minPrev 改指 8；后续 6、9 不更小，不再变。

原局部：8 → 3 → 6 → 9
步骤一：3.next = 6.next，把 3 改接到 9
步骤二：6.next = 3，把 6 改接到 3
步骤三：8.next = 6，把前面的入口接到 6
最终：  8 → 6 → 3 → 9

步骤二后会出现暂时的 6→3→9 分支，但前驱 8 还没接它；步骤三把整个局部接回主链，所以不能只改最小与后继两根箭头就结束。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool handleMinNode(LinkList L) {
    if (L == NULL || L->next == NULL)
        return false;

    LinkList minPrev = L;
    for (LinkList p = L; p->next != NULL; p = p->next) {
        if (p->next->data < minPrev->next->data)
            minPrev = p;
    }

    LinkList minNode = minPrev->next;
    LinkList successor = minNode->next;
    if (successor == NULL)
        return false;

    if (minNode->data % 2 == 0) {
        minNode->next = successor->next;
        free(successor);
    } else {
        minNode->next = successor->next;
        successor->next = minNode;
        minPrev->next = successor;
    }

    return true;
}

第一条 if 排除空入口和空表。minPrev 先设为 H，表示暂认首结点最小。for 从 p=H 开始，只要 p 后面有结点就比较，较小时保存 p 而不是 p->next，这样保留了前驱。

找完再取 minNode、successor。如果后继为 NULL，无法交换或删除，返回 false。data%2==0 是偶数分支：让 minNode 跳过 successor，再 free 后者；奇数分支则按上面三步交换结点，没有交换 data。最后 true 只表示成功完成操作。

4. 自己试一下

输入 H→8→2→6→9：保留 2，让 2 指 9，释放 6，输出 H→8→2→9。若最小结点在末尾，例如 H→8→3，则返回 false，不能访问 3 的不存在的后继。若交换 data 而不改箭头，结点身份没交换，不满足题意。

学懂后回看：结论、复杂度与回源

题意与结论：无序正整数链表中最小值唯一。若最小值是奇数，交换它与后继的结点位置；若是偶数，删除它的后继。必须记录最小结点的前驱 minPrev。

思路推导：只找到最小结点还不够，交换时要修改“它前面的那条边”。单链表不能从当前结点直接找到前驱，所以搜索时就把前驱留下。

走一遍：L→8→3→6→9，最小值 3 为奇数。局部为 8→3→6→9：先 3.next=9，再 6.next=3，最后 8.next=6，得到 8→6→3→9。若原表为 8→2→6→9，2 为偶数，则令 2.next=9 并释放 6，得到 8→2→9。

代码抓手与正确性：遍历中比较 p->next->data 与 minPrev->next->data。搜索完成后，minNode=minPrev->next，successor=minNode->next。先判断后继非空，再进入删除或交换。三个连接修改将原局部 前驱→最小→后继→余链 重排为目标形式，其余链不受影响。

复杂度与易错点：时间 O(n)，空间 O(1)。最小值在末尾就返回失败，不能访问 NULL。交换的是结点位置，不能偷换成交换 data；偶数情况删的是后继，不是最小结点。释放后不能再读取该结点。

回源：PDF 第 10 页；回源 · PDF 第 10 页 · b_10_3 。正式代码

18｜有序链表去重（本章第 3 题）

题目与要求

题目（依据原题整理）：设计尽可能高效的算法，删除递增有序单链表中的重复结点，每种值只保留第一次出现的结点。

已知条件：输入带头结点的有序单链表；这里“递增”允许相等值，相同值的结点必然相邻。

需要得到：仍然有序、没有重复值的链表；删除的是多余结点，不只是把它们的数据改成某个标记。

输入 → 输出示例（教学补充）：L→1→1→2→2→2→4→NULL → L→1→2→4→NULL。

约定与提醒（教学补充）：同值的一组要留下第一个，并释放后面多余的数据结点；头结点不能删除。空链表保持为空链表。

题干回源：Code59 PDF 第 10 页；回源 · PDF 第 10 页 · b_10_5 。

1. 删除重复结点，不是仅把值打印一次

输入 H→1a→1b→1c→2→3a→3b，a、b、c 只是用来区分同值的不同结点；data 仍分别为 1 或 3。输出要真正留下 H→1a→2→3a，其他结点摘除并释放。

p 指目前已经保留的结点，duplicate 临时指要删的那个后继。

2. 为什么删完一个 1，p 还要站着不动

当前 p	它的后继	判断与动作	下一次 p
1a	1b	data 相等，删 1b，1a 改连 1c	仍是 1a
1a	1c	还是相等，删 1c，1a 改连 2	仍是 1a
1a	2	不等，当前段结束	前进到 2
2	3a	不等	前进到 3a
3a	3b	相等，删 3b	仍是 3a
3a	NULL	无后继可比较	停止

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void uniqueOrderedList(LinkList L) {
    LinkList p = L->next;

    while (p != NULL && p->next != NULL) {
        if (p->data == p->next->data) {
            LinkList duplicate = p->next;
            p->next = duplicate->next;
            free(duplicate);
        } else {
            p = p->next;
        }
    }
}

p 初始 L->next，跳过不存有效数据的头结点。while 同时保证 p 和 p 的后继存在，才能读两边 data。若相等，先 duplicate=p->next 记住要删除的地址；再 p->next=duplicate->next 把链跳过它；最后 free。这个顺序保证不会释放后才去读它的 next。

else 才执行 p=p->next，表示换一个保留值继续检查。p 不动不意味着没有进展：重复分支每次实实在在少了一个结点，最终总会结束。

4. 自己试与反例

若删完 1b 就让 p 前进到 1c，那么以后再也不会比较 1a 与 1c，最后可能留下两个 1。练习 [2,2,3,3]：删除第二个 2 后不动，再遇 3 才前进，最后删除第二个 3，得到 [2,3]。若输入无序 [2,3,2]，相邻比较看不见远处重复，题设不能省。

学懂后回看：结论、复杂度与回源

题意与结论：相同值连续出现，保留首结点，删除它后面所有同值结点。删后继后，当前指针不前进。

思路推导：数组去重要覆盖搬移；链表可以直接把重复结点从连接中跳过去。当前结点已经保留，只需检查它的后继是不是重复。

走一遍：1a→1b→1c→2→3a→3b。p 指向 1a，删 1b 后 p 仍是 1a，再比较新后继 1c，继续删除；遇到 2 才移动 p。最终剩 1a→2→3a，保留的是各值第一次出现的原结点。

代码抓手与正确性：重复时先 q=p->next，再 p->next=q->next，最后 free(q)；不重复才 p=p->next。每轮要么删掉一个结点，要么向前走一个结点，因此不会重复无效扫描。

复杂度与易错点：时间 O(n)，空间 O(1)。循环需同时保证 p 与 p 的后继存在。若每轮无条件 p=p->next，连续三个相同值会漏删。不能把头结点的数据域拿来比较。

回源：PDF 第 10 页；回源 · PDF 第 10 页 · b_10_5；PDF 第 10 页 · b_10_6；PDF 第 10 页 · b_10_8 。正式代码

19｜按绝对值去重（本章第 4 题，2015）

题目与要求

题目（依据原题整理）：一个单链表保存 m 个整数，每个数满足 |data|<=n。设计时间上尽可能高效的算法：对绝对值相同的结点，仅保留第一次出现的那个，删除其余结点。

已知条件：输入带头结点的链表以及绝对值上界 n；m 是结点个数，n 是数值范围，两者不是同一个量。

需要得到：按绝对值去重的链表，保留结点的数值与原有先后顺序不变。

输入 → 输出示例（教学补充）：L→-3→3→2→-2→0→0→NULL，n=3 → L→-3→2→0→NULL。

约定与提醒（教学补充）：-3 和 3 算同一类，但留下 -3 时不能把它改写为 3。本题允许辅助标记数组；需要把取值 0 也纳入范围。

题干回源：Code59 PDF 第 10—11 页；回源 · PDF 第 10 页 · b_10_9；PDF 第 11 页 · b_11_0 。

1. 相同绝对值是同一类，但保留原来的正负号

输入 21→-15→-21→-7→15，输出 21→-15→-7。21 与 -21 算一类，-15 与 15 算一类；先来谁就留下谁。不是把链表全部改成正数再去重。

seen 是按绝对值编号的签到表。value 是原带符号的数，key 是去掉符号后的类别编号。p 站在“待检查结点的前面”，初始站 H。

2. 对每个结点决定“留”还是“摘下”

待检查值	key	seen[key] 原来怎样	操作
21	21	假	标记为真，保留，p 前进到 21
-15	15	假	标记为真，保留，p 前进到 -15
-21	21	真	从 -15 后面摘掉 -21，p 仍在 -15
-7	7	假	保留，p 前进到 -7
15	15	真	删除，p 仍在 -7

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool uniqueByAbsoluteValue(LinkList L, int n) {
    bool *seen = (bool *)calloc(n + 1, sizeof(bool));
    if (seen == NULL)
        return false;

    LinkList p = L;
    while (p->next != NULL) {
        int value = p->next->data;
        int key = value >= 0 ? value : -value;

        if (!seen[key]) {
            seen[key] = true;
            p = p->next;
        } else {
            LinkList duplicate = p->next;
            p->next = duplicate->next;
            free(duplicate);
        }
    }

    free(seen);
    return true;
}

calloc 申请 n+1 个布尔格，使 0..n 都能作为下标。失败返回 false。每轮读取 p->next->data，三目表达式 value>=0 ? value : -value 得到 key。

!seen[key] 表示该类别还没留下过结点，于是标记并前进；否则按“保存重复地址→前驱绕过它→释放”的三步删除，p 不动，好让新后继被检查。循环结束 free 的 seen 是辅助签到表，不是剩下的整条链表。

4. 自己试一下

[-3,3,-3,0,0] 应留下 [-3,0]。负数 -3 第一次出现，所以留下它，而不是等正数 3。0 也需要一个标记格，不能只申请 n 个而又访问 seen[n]。若有 m 个结点、值域上界 n 很大，初始化 n 个标记也花时间，所以完整时间是 O(m+n)。

学懂后回看：结论、复杂度与回源

题意与结论：共有 m 个结点，满足 |data|<=n。把绝对值当作同类标记，保留每类第一次出现的结点，用 seen[0..n] 判重。

思路推导：逐个结点再扫描其后是否同绝对值，最坏 O(m²)。题目给出的值域允许直接查表：seen[abs(x)] 为真说明已经保留过这一类，不需要再找那一个结点。

走一遍：21→-15→-21→-7→15，假设 n>=21。保留 21 并标记 21；保留 -15 并标记 15；遇 -21 发现 21 已标记，删除；保留 -7；遇 15 发现 15 已标记，删除。得到 21→-15→-7，并不是把所有值都变为正数。

代码抓手与正确性：p 指向待检查结点的前驱。首次出现时标记并移动 p；重复时摘除 p->next、释放，p 不动。已处理部分每个绝对值恰留一个最先出现的结点，后续判重只依赖标记。

复杂度与易错点：完整时间 O(m+n)，因为标记数组初始化也要 O(n)；空间 O(n)。不能把 m、n 混成一个长度。0 的绝对值还是 0，数组要包含这一槽；工程上要防 abs(INT_MIN) 溢出，并保证值域与分配成功，考试按题设范围处理。

回源：PDF 第 10—11 页；回源 · PDF 第 10 页 · b_10_9；PDF 第 11 页 · b_11_0；PDF 第 11 页 · b_11_6 。正式代码

20｜按正负稳定拆分（本章第 5 题）

题目与要求

题目（依据原题整理）：把带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B：A 保留值大于或等于 0 的结点，B 保存值小于 0 的结点。

已知条件：输入 A，数据可以有负数、0 和正数；0 必须留在 A。

需要得到：修改后的 A 和新表 B，每个原数据结点恰好属于其中一个表。

输入 → 输出示例（教学补充）：A→2→-1→0→-3→NULL → A→2→0→NULL，B→-1→-3→NULL。

约定与提醒（教学补充）：本讲解采用稳定拆分，也就是两组内保留原相对次序；这是下面实现具备的性质。复用原数据结点，仅为 B 新建头结点，不能把 B 当作数组下标或某个负数。

题干回源：Code59 PDF 第 11 页；回源 · PDF 第 11 页 · b_11_1 。

1. 拆成两条链，但不改变各自的排队次序

输入 A=[3,-2,0,-5,4]。输出 A=[3,0,4]、B=[-2,-5]。非负数留下，负数拿走接到 B 尾部。B 需要一个新头结点，但数据结点都是原来那些。

p 是 A 中待检查结点的前驱；tailB 是 B 当前最后一个结点，B 为空时它就是 B 的头结点。

2. 逐次跟踪两条链的有效连接

检查谁	A 中的处理	B 的结果	p、tailB
3	留下	空	p=3，tailB=B头
-2	3 绕过 -2 接 0	B 接入 -2	p=3，tailB=-2
0	留下	仍为 -2	p=0
-5	0 绕过 -5 接 4	-2 后接 -5	p=0，tailB=-5
4	留下	-2→-5	p=4
扫完	A=3→0→4	B 尾 next 置 NULL	两链独立结束

搬运过程里 B 尾部可能暂留通往旧 A 后继的箭头，因此上表 B 结果指“已选入 B 的部分”；最后的置空才切断旧尾连接。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

LinkList splitBySign(LinkList A) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    if (B == NULL)
        return NULL;

    B->next = NULL;
    LinkList p = A;
    LinkList tailB = B;

    while (p->next != NULL) {
        if (p->next->data >= 0) {
            p = p->next;
        } else {
            LinkList node = p->next;
            p->next = node->next;
            tailB->next = node;
            tailB = node;
        }
    }

    tailB->next = NULL;
    return B;
}

malloc 只申请 B 的头结点；失败返回 NULL。先把 B->next 设空，p=A，tailB=B。while 看的是 p 后面有没有待检查数据结点。

非负分支仅移动 p，不改数据。负数分支 node=p->next 先保存地址；p->next=node->next 把它从 A 摘下；tailB->next=node 接到 B；tailB=node 更新尾书签。此分支不能前进 p，因为摘掉后它的新后继还没看。末尾 tailB->next=NULL 收尾，再返回新头结点 B 的地址。

4. 自己试与错误改法

若把每个负数都插 B 最前面，-5 会跑到 -2 前面，违反保序。输入全负数 [-1,-2]：A 只剩头结点，B 为 -1→-2；全非负 [0,2]：B 仍是一个 next 为 NULL 的空头结点，不应返回 NULL 冒充申请失败。

学懂后回看：结论、复杂度与回源

题意与结论：A 留非负结点，B 收负结点，两条链都保持原来的相对顺序。负结点从 A 摘下，尾插到 B。

思路推导：头插会逆序，因此本题要维护 tailB。A 中非负结点不挪动，只跳过被摘走的负结点，本身就保持次序。

走一遍：A=[3,-2,0,-5,4]。3 留 A；摘 -2，B 为 [-2]；0 留 A；摘 -5，接到 B 尾部，B 为 [-2,-5]；4 留 A。最终 A 为 [3,0,4]，B 为 [-2,-5]。

代码抓手与正确性：p 是待处理结点的前驱。非负时 p=p->next；负数时 node=p->next、p->next=node->next，然后 tailB->next=node; tailB=node。删除后 p 不动，继续处理它的新后继。每个原结点被分到且只分到一个链中。

复杂度与易错点：时间 O(n)，除新建 B 头结点外工作空间 O(1)。结束必须 tailB->next=NULL，否则尾结点可能仍通过旧指针连回 A。0 归 A；全负、全非负均可。没有释放被搬到 B 的数据结点。

回源：PDF 第 11 页；回源 · PDF 第 11 页 · b_11_1；PDF 第 11 页 · b_11_3；PDF 第 11 页 · b_11_7 。正式代码

21｜交替链拆成 a 正序、b 逆序（本章第 6 题）

题目与要求

题目（依据原题整理）：单链表的元素依次为 (a1,b1,a2,b2,…,an,bn)。将它拆成两个链表：A=(a1,a2,…,an)，B=(bn,…,b2,b1)。

已知条件：输入表按 a、b 交替排列，共有 2n 个数据结点；本章用带头结点结构表示它。

需要得到：a 组保持正序，b 组逆序，复用原数据结点完成拆分。

输入 → 输出示例（教学补充）：A→1→10→2→20→3→30→NULL → A→1→2→3→NULL，B→30→20→10→NULL。

约定与提醒（教学补充）：分组依据是原来的第 1、3、5…与第 2、4、6…个位置，不是数值的奇偶。示例的 2 虽是偶数，仍属于 a 组。

题干回源：Code59 PDF 第 11 页；回源 · PDF 第 11 页 · b_11_2；PDF 第 11 页 · b_11_4；PDF 第 11 页 · b_11_8 。

1. 这里按“原位置”分类，不按数字奇偶

输入 a1→b1→a2→b2→a3→b3，A 要 a1→a2→a3，B 要 b3→b2→b1。符号 a1 等表示结点身份，不要求 data 是特定数字。

position 记录已经走到原序列第几位，从 1 开始。奇数位置留 A，偶数位置头插 B，所以 b 的次序自动反转。

2. 用六个名字看次序怎么变

原位置	当前结点	动作	B 的已选部分
1	a1	留 A，p 前进	空
2	b1	摘下，放 B 最前面	b1
3	a2	留 A，p 前进	b1
4	b2	摘下，指向原 B 首 b1，再让 B 指 b2	b2→b1
5	a3	留 A，p 前进	b2→b1
6	b3	同样头插	b3→b2→b1

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

LinkList splitAlternating(LinkList A) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    if (B == NULL)
        return NULL;

    B->next = NULL;
    LinkList p = A;
    int position = 1;

    while (p->next != NULL) {
        if (position % 2 == 1) {
            p = p->next;
        } else {
            LinkList node = p->next;
            p->next = node->next;
            node->next = B->next;
            B->next = node;
        }
        position++;
    }

    return B;
}

申请并初始化 B 头结点。p=A 表示从 A 头后面检查，position=1。position%2==1 时当前原位置属于 a，只移动 p；否则存 node、从 A 绕过去，再执行 node->next=B->next 和 B->next=node，先接旧首、再改入口。

每轮最后 position++，不论保留还是搬走都算“处理了一个原结点”。删除分支 p 不动，但 position 必须动，这两个变量记录的东西不同：p 是当前链中的地址，position 是原序列的处理进度。

4. 自己试一下

把原结点 data 设成 [8,7,6,5]：A 留的是第 1、3 位 [8,6]，B 是原第 4、2 位 [5,7]；不是“偶数放 A、奇数放 B”这个数值判断。尾插 b 会得到 b1、b2、b3，正好与本题相反。

学懂后回看：结论、复杂度与回源

题意与结论：a1,b1,a2,b2,...,an,bn 拆为 A 的 a1,...,an 与 B 的 bn,...,b1。原奇数位置保留，原偶数位置摘下头插 B。

思路推导：a 要保持原顺序，所以留在原链；b 要反序，头插恰好完成。无需先拆完再逆置一次。

走一遍：a1→b1→a2→b2→a3→b3。保留 a1，摘 b1 后 B 为 [b1]；保留 a2，摘 b2 头插后 B 为 [b2,b1]；保留 a3，再头插 b3，B 为 [b3,b2,b1]。A 最终为 [a1,a2,a3]。

代码抓手与正确性：position 统计的是原链依次处理到第几个结点，不是当前剩余链的下标。每轮都 position++。奇数位置 p 前进；偶数位置摘走后 p 不动，再执行 node->next=B->next; B->next=node。

复杂度与易错点：时间 O(n)（原链有 2n 个结点，仍为线性），空间 O(1)。按“位置奇偶”拆，不是按 data 的奇偶拆。B 用尾插就会得到 b 正序，与要求相反。

回源：PDF 第 11 页；回源 · PDF 第 11 页 · b_11_2；PDF 第 11 页 · b_11_4；PDF 第 11 页 · b_11_8 。正式代码

22｜两有序链表原地归并（本章第 7 题）

题目与要求

题目（依据原题整理）：两个单链表 A、B 各自递增有序。设计一个算法，将 B 合并到 A 中，使结果仍为非递减有序链表，并使用原有结点空间。

已知条件：两表都有头结点，各自以 NULL 结束；两个输入表的数据结点互不共享。

需要得到：在 A 的头结点之后连接两表的全部数据结点，按从小到大排列，重复值也要保留。

输入 → 输出示例（教学补充）：A→1→3→NULL，B→2→3→NULL → A→1→2→3→3→NULL。

约定与提醒（教学补充）：“原地归并”是重新接原结点，不是复制成一条新链。合并后不能再把旧 B 的数据链当作一条独立拥有的链表重复操作或释放；两表之一为空时，也要保留另一表全部元素。

题干回源：Code59 PDF 第 12 页；回源 · PDF 第 12 页 · b_12_0 。

1. 和数组归并相同的比较，不同的搬法

A=1→4a→7、B=2→4b→6。目标用 A 头结点接 1→2→4a→4b→6→7。4a、4b 数值相同，但都是要保留的原结点。

p、q 指两链尚未使用的首结点；tail 指已经拼好的结果末结点，初始是 A 的头结点。这里 tail->next=p 是接入一个结点地址，不是把 p 的 data 复制给 tail。

2. 每次接完以后，谁移动？

p 的值、q 的值	接入谁	输入书签怎样变	tail 变成谁
1、2	p 的 1	p 前进到 4a，q 不动	1
4、2	q 的 2	q 前进到 4b	2
4、4	p 的 4a	p 前进到 7	4a
7、4	q 的 4b	q 前进到 6	4b
7、6	q 的 6	q 到 NULL	6
B 耗尽	p 剩下的整串 7	直接接到结果尾	无须再逐个比较

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void mergeOrderedLists(LinkList A, LinkList B) {
    LinkList p = A->next;
    LinkList q = B->next;
    LinkList tail = A;

    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }

    tail->next = (p != NULL) ? p : q;
    B->next = NULL;
}

最前三句保存两条输入入口与输出尾入口。while 两边均非空才比较；A 小或相等时接 p 并移动 p，否则接 q 并移动 q。花括号外 tail=tail->next 是共同收尾，走到刚接入的结点。

最后的三目表达式 p!=NULL ? p : q 表示哪边还有剩余就接哪边，全空也会接 NULL。B->next=NULL 清空 B 的旧入口，数据结点现在已经属于 A 的结果链，不能再通过 B 当作另一份独立链重复释放。

4. 自己试一下

A 空、B=2→5：主循环不执行，tail 仍指 A 头，最后一条拼接让 A 直接接 2→5，B 头清空。若写成 tail=p 而漏写 tail->next=p，只是移动书签，没有把链连接起来。默认输入不共享结点，公共后缀那种输入需另行处理。

学懂后回看：结论、复杂度与回源

题意与结论：复用 A、B 原有数据结点，按非递减次序接到 A 的头结点之后。p、q 各指一个最小未处理结点，较小者尾插。

思路推导：与数组归并比较规则相同，但不用复制数据到新数组，只改链接即可。每次选择当前两头较小的一方，它就是全局最小剩余结点。

走一遍：A=[1,4,7]，B=[2,4,6]。依次接入 A1、B2、A4、B4、B6；B 用完后，直接把 A 剩下的 [7] 整段接上。结果 [1,2,4,4,6,7]。

代码抓手与正确性：tail 指向结果最后一个结点；每接入一个结点，移动对应输入指针，再让 tail 前进。主循环结束用 tail->next=(p!=NULL?p:q) 拼剩余部分，最后清空 B 头结点的 next，避免把 B 当成仍独立拥有那些结点的链。

复杂度与易错点：时间 O(m+n)，空间 O(1)。这是归并，重复值不删。默认两条输入链不共享数据结点；共享结点时直接套用可能破坏结构。不能释放已经被结果链复用的结点，后续也不能对同一结点重复释放。

回源：PDF 第 12 页；回源 · PDF 第 12 页 · b_12_0 。正式代码

23｜两个有序链表的去重并集（本章第 8 题）

题目与要求

题目（依据原题整理）：A、B 是递增有序单链表。求两者所有元素的并集，去掉重复值后存回 A，要求使用 A 和 B 原有的结点空间。

已知条件：两表带头结点、无环且数据结点互不共享；锁定校订实现也处理单个表内部已有的重复值。

需要得到：在 A 中按从小到大排列所有出现过的不同值，每种值只保留一个结点。

输入 → 输出示例（教学补充）：A→1→1→3→NULL，B→1→2→3→NULL → A→1→2→3→NULL。

约定与提醒（教学补充）：第 22 题保留所有重复值，本题则必须去重；不能只检查跨表重复而漏掉表内重复。下面函数复用保留结点并释放多余结点，结果不是两表的独立副本。

题干回源：Code59 PDF 第 12 页；回源 · PDF 第 12 页 · b_12_1 。表内去重是锁定稿明确补齐的校订内容。

1. 并集比上一题多了“每个值只能留下一个”

A=[1,1,3]、B=[1,2,2,3]，输出 [1,2,3]。重复不仅可能来自两表之间，也可能在 A 自己或 B 自己内部。

除了 p、q、tail，还要 lastValue 记上次真正留下的值，hasLast 记“结果里已经有值了吗”。空结果时不能凭 lastValue=0 就认定 0 已经出现。

2. 跟着候选结点过两道检查

第一道按大小合并，得到候选；第二道与最近保留值比较，决定留下还是释放。

候选过程	检查	结果链
A 首 1 与 B 首 1 相等	用 A 的 1，先释放 B 的一个 1	1
A 下一个还是 1	与 lastValue=1 相同，释放	1
B 当前为 2	与 1 不同，留下并更新 lastValue=2	1→2
B 下一个仍为 2	重复，释放	1→2
两边最后都是 3	留一个、释放另一个	1→2→3

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void unionOrderedLists(LinkList A, LinkList B) {
    LinkList p = A->next;
    LinkList q = B->next;
    LinkList tail = A;
    bool hasLast = false;
    int lastValue = 0;

    A->next = NULL;
    B->next = NULL;

    while (p != NULL || q != NULL) {
        LinkList node;

        if (q == NULL || (p != NULL && p->data <= q->data)) {
            node = p;
            p = p->next;

            if (q != NULL && node->data == q->data) {
                LinkList duplicate = q;
                q = q->next;
                free(duplicate);
            }
        } else {
            node = q;
            q = q->next;
        }

        if (!hasLast || node->data != lastValue) {
            tail->next = node;
            tail = node;
            lastValue = node->data;
            hasLast = true;
        } else {
            free(node);
        }
    }

    tail->next = NULL;
}

先存 p、q 再清空两个头结点的 next，原数据串仍由工作指针保存。while 使用 ||：只要还有一边没处理完就继续，而不是两边都在才继续。

q==NULL || (p!=NULL && p->data<=q->data) 的意思是“B 已空，或 A 存在且不大于 B”，这时取 A。短路条件保护空指针不被读取。取走前先保存 node，再移动输入指针；若另一边正好同值，可以顺便释放一个跨表副本。

候选到手后，!hasLast || node->data!=lastValue 说明结果为空或是新值，才接到 tail 后、更新 tail 和 lastValue、设 hasLast=true。否则只释放 node，不移动结果尾。最后把 tail 的 next 设 NULL，截掉可能残留的旧链接。

4. 自己试与为什么不能省第二道检查

A=[2,2]、B 为空，跨表相等条件永远不成立；若没有 lastValue 检查，两个 2 都留下了。正确做法第一候选 2 留下、第二候选 2 释放，结果 [2]。释放一个候选之前，它的旧后继必须已被 p 或 q 保存，不能释放后再去找路。

学懂后回看：结论、复杂度与回源

题意与结论：结果每种值只保留一次，存回 A，并复用原结点。除归并时去掉跨表重复，还要与结果最后保留值比较，去掉单表内部重复。

思路推导：只处理 p->data==q->data 不够。例如 A 自己有两个 1，而 B 没有 1，单靠跨表比较会让两个 1 都进入结果。因为输出候选已按序排列，只需记住最近保留的值。

走一遍：A=[1,1,3]，B=[1,2,2,3]。两头都是 1，保留一个、释放另一个；A 剩下的第二个 1 与结果末值相同，释放；遇 2 保留，第二个 2 释放；遇 3 保留一个。最终 [1,2,3]。

代码抓手与正确性：hasLast 表示是否已有结果，不能用某个数字当“还没有值”的哨兵；lastValue 只在真正接入结点时更新。所有待选结点按非递减序到来，与上一个保留值不同就意味着新的一类；相同就可安全删除。

复杂度与易错点：时间 O(m+n)，空间 O(1)。被删除的重复结点要释放；先保存其后继再释放；最后 tail->next=NULL。正式校订版已补齐单表内部去重。与上一题相同，默认输入链不共享数据结点。

回源：PDF 第 12 页；回源 · PDF 第 12 页 · b_12_1；PDF 第 12 页 · b_12_3；PDF 第 12 页 · b_12_2 。正式代码

24｜两个单词链的公共后缀（本章第 9 题，2012）

题目与要求

题目（依据原题整理）：用带头结点的单链表保存单词，每个数据结点存一个字符。两个单词具有相同后缀时，可以共享这部分结点空间。str1、str2 分别指向两表的头结点，设计时间上尽可能高效的算法，找出公共后缀的起始结点。

已知条件：两表无环，可以长短不同；共享后缀是实际共用同一批结点，而不只是字符相同。

需要得到：第一个共享结点的地址；不存在共享结点时返回 NULL。

输入 → 输出示例（教学补充）：loading 与 being 的两条字符链，如果实际共用末尾同一条 i→n→g→NULL 子链，则返回这个共享的 i 结点。

约定与提醒（教学补充）：如果两条链只是各自存了字符 ing，但对应结点地址不同，就没有本题所说的公共后缀。算法不修改原链表。

题干回源：Code59 PDF 第 13 页；回源 · PDF 第 13 页 · b_13_0；PDF 第 13 页 · b_13_1 。

1. 相同字母不等于同一块存储

假设 A=a→b→X→Y→Z，B=c→X→Y→Z，大写部分是真正共享的同一批结点。目标返回 X 的地址。若只是两条独立链碰巧都写了 X、Y、Z，而结点地址不同，不算共享。

len1、len2 是剩余长度；p、q 是两边当前地址。先对齐“离终点还有多远”，再一起走。

2. 不对齐会错过，同时到达才好比较

动作	p	q	剩余结点数
从首数据结点出发	a	c	5、4
A 长一格，先走一步	b	c	4、4
比较地址	b 与 c 不同	—	保持同样远
两边一起走一步	X	X	3、3
比较地址相等	返回 X	—	后面自然全共享

链式结构里一个结点只有一个 next，因此一旦两指针真的落到同一个结点上，后面的路线必然相同，不会又分岔。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int listLength(LinkList L) {
    int length = 0;
    for (LinkList p = L->next; p != NULL; p = p->next)
        length++;
    return length;
}

LinkList firstCommonSuffixNode(LinkList str1, LinkList str2) {
    int len1 = listLength(str1);
    int len2 = listLength(str2);
    LinkList p = str1->next;
    LinkList q = str2->next;

    while (len1 > len2) {
        p = p->next;
        len1--;
    }
    while (len2 > len1) {
        q = q->next;
        len2--;
    }

    while (p != NULL && q != NULL) {
        if (p == q)
            return p;
        p = p->next;
        q = q->next;
    }

    return NULL;
}

listLength 从 L->next 起，每访问一个数据结点 length++，不计头结点。主函数先调用两次数长度，再设置 p、q 为各自首数据结点。

第一个 while 处理 A 更长：p 前进、len1 减一；第二个 while 对称处理 B 更长；两者至少一段不会执行。之后长度相等，两指针同步走，p==q 比较地址而非 data，第一次相等立即返回该地址。都找不到就返回 NULL。

4. 自己试一下

若 A 长 7、B 长 4，先让谁走几步？答案：A 的 p 先走 3 步，B 不动。若两链完全共享首数据结点，长度相同且第一次比较就相等。若都含字符 a，但它们是两块不同结点，p->data==q->data 可能真，p==q 仍是假。

学懂后回看：结论、复杂度与回源

题意与结论：找两链真正共享的后缀起点，比较结点地址而不是字符。先让较长链走长度差，两指针距表尾一样远，再同步前进。

思路推导：如果分别从表头一起走，长链到公共结点时短链可能早已走过它。对齐剩余长度，就能让它们同时到达共享后缀的同一位置。单链表一旦指向同一个结点，后续 next 也相同，因此之后整个尾部必共享。

走一遍：A 为 a→b→X→Y→Z，B 为 c→X→Y→Z，其中大写表示同一批实际结点。长度 5 和 4，A 先走一步到 b。同步比较 (b,c) 不同，再走一步 (X,X) 地址相同，返回 X。

代码抓手与正确性：计算长度不含头结点；对齐后用 if(p==q) 判断。即使两边 data 都是字符 x，只要是两个分别申请的结点，就不构成共享后缀。同步遍历第一个相同地址，正是最早共享位置。

复杂度与易错点：时间 O(m+n)，空间 O(1)。无公共结点时返回 NULL；完全共享则返回首数据结点。前提是无环链，不能把环中相遇问题混进来。本题不修改或释放任何结点。

回源：PDF 第 12—13 页；回源 · PDF 第 13 页 · b_13_0；PDF 第 13 页 · b_13_1；PDF 第 13 页 · b_13_2；PDF 第 12 页 · b_12_4；PDF 第 12 页 · b_12_5 。正式代码

25｜倒数第 k 个结点（本章第 10 题，2009）

题目与要求

题目（依据原题整理）：在单链表中查找倒数第 k 个数据结点。找到时输出该结点的 data 并返回 1；未找到时返回 0。设计算法实现这一功能。

已知条件：输入带头结点的单链表 L 和整数 k；从最后一个数据结点算倒数第 1 个，头结点不参与计数。

需要得到：成功时打印目标数据，并另行返回成功标志；不改变链表。

输入 → 输出示例（教学补充）：L→10→20→30→40→NULL，k=2 → 输出 30，返回 1；同一链表 k=5 → 返回 0。

约定与提醒（教学补充）：函数返回的 1 不是结点值，结点值由打印语句输出。k<=0、空表或数据结点不足 k 个都属于查找失败。

题干回源：Code59 PDF 第 13 页；回源 · PDF 第 13 页 · b_13_3 。

1. 倒数第 k 个，把终点距离放进两指针之间

输入 10→20→30→40→50、k=2。倒数第 1 个是 50，第 2 个是 40；输出 40 并返回成功标志 1。k 不是数组下标，从 1 起数。

fast 先走，slow 后走。保持两者相隔 k 条 next 箭头，fast 走到末尾后的 NULL 时，slow 正好距表尾 k 个结点。

2. 把“先走两步”与“一起走”分开

阶段	slow	fast
两者从首数据结点出发	10	10
fast 单独第 1 步	10	20
fast 单独第 2 步	10	30
同步第 1 步	20	40
同步第 2 步	30	50
同步第 3 步	40	NULL，循环停止

不要等 fast 指尾结点 50 时就停；这份模板等的是 fast 变 NULL，所以提前步数才是 k。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int printKthFromEnd(LinkList L, int k) {
    if (L == NULL || k <= 0)
        return 0;

    LinkList fast = L->next;
    LinkList slow = L->next;

    for (int i = 0; i < k; i++) {
        if (fast == NULL)
            return 0;
        fast = fast->next;
    }

    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    printf("%d", slow->data);
    return 1;
}

先排除无效头指针与 k<=0。两个指针从 L->next 而非 L 出发。for 恰执行 k 次，每次先检查 fast 是否已经空，再前进；若没走足 k 步就空，说明链不够长，返回 0。

第二个 while 只要 fast 还非空，fast、slow 各走一步，间隔不变。停止后 slow 有效，printf 输出它的 data；return 1 表示找到了。这个函数并不返回结点地址，也不返回 data 本身。

4. 自己试一下

[7,8,9]、k=3：fast 先走 3 步就到 NULL，slow 一直在 7，同步循环不进，答案为 7。k=4 时，提前阶段第 4 次检查发现 fast 已空，失败。不必先计算表长来判断超长，这个检查已经完成了它。

学懂后回看：结论、复杂度与回源

题意与结论：成功时输出结点 data 并返回 1，失败返回 0。快指针先走 k 步，再与慢指针同速走；快指针到 NULL，慢指针就在倒数第 k 个。

思路推导：可以先数长度再走到第 n-k+1 个；双指针把“距尾部 k 个位置”的关系直接保存在两个指针的间距里，无须先得出 n。

走一遍：10→20→30→40→50，k=2。两指针从 10 开始，快指针先走到 30，慢指针仍在 10。同步走：(慢20,快40)、(慢30,快50)、(慢40,快NULL)，输出 40 并返回 1。

代码抓手与正确性：快指针提前每走一步前都检查非空；若没走满 k 步就到 NULL，则 k 超长。同步阶段始终保持 k 条 next 跨度，因此快指针走到尾后空位置时，从慢指针所指结点到表尾恰有 k 个结点。

复杂度与易错点：时间 O(n)，空间 O(1)。k=1 找尾结点，k=n 找首结点，k<=0 或 k>n 失败。注意这里从首数据结点出发；若改从头结点出发，步数必须重新推，不要混抄另一套模板。

回源：PDF 第 13 页；回源 · PDF 第 13 页 · b_13_3；PDF 第 13 页 · b_13_7；PDF 第 13 页 · b_13_4；PDF 第 13 页 · b_13_5 。正式代码

26｜重排为 a1、an、a2、an-1……（本章第 11 题，2019）

题目与要求

题目（依据原题整理）：给定单链表 L=(a1,a2,…,an)，将它重新排列为 (a1,an,a2,an-1,a3,an-2,…)，也就是依次取原来的首端、尾端、次首端、次尾端，直到全部结点排完。

已知条件：输入带头结点的无环单链表，n 可以为奇数，也可以为偶数。

需要得到：在原链表上重接结点，每个结点恰好使用一次，不另建一份数据链表。

输入 → 输出示例（教学补充）：L→1→2→3→4→5→NULL → L→1→5→2→4→3→NULL。

约定与提醒（教学补充）：a1、an 是原位置的名字，不代表要按数值大小排序。奇数长度时中间结点只出现一次，最后仍须以 NULL 结束，不能误接成环。

题干回源：Code59 PDF 第 14 页；回源 · PDF 第 14 页 · b_14_0；PDF 第 14 页 · b_14_1 。

1. 把“反复找最后一个”改成“排好两串轮流拿”

输入 1→2→3→4→5，目标 1→5→2→4→3。若每次从头找尾，找 5 一遍、找 4 又一遍，会重复很多工作。先拆成前半 [1,2,3]、后半 [4,5]，把后半逆成 [5,4]，再轮流取就方便了。

这里有两种快慢指针用途：第一阶段找中点，不是判环；之后 first、second 分别扫两段，不再一快一慢。

2. 三个阶段要分别画，不要一口气追六个指针

阶段	状态
找中点初始	slow=1，fast=1
同时移动一次	slow=2，fast=3
再移动一次	slow=3，fast=5；fast 后面无两步，停
逆置后半	从 slow->next 即 4 开始，得到 5→4→NULL
断开前半	slow->next=NULL，前半 1→2→3→NULL
第一次穿插	保存 nextFirst=2、nextSecond=4；接 1→5→2
第二次穿插	保存 nextFirst=3、nextSecond=NULL；接 2→4→3
收尾	second=NULL，最终 1→5→2→4→3

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

LinkList reverseWithoutHead(LinkList head) {
    LinkList previous = NULL;
    LinkList current = head;

    while (current != NULL) {
        LinkList next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

void reorderList(LinkList L) {
    if (L == NULL || L->next == NULL || L->next->next == NULL)
        return;

    LinkList slow = L->next;
    LinkList fast = L->next;

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    LinkList second = reverseWithoutHead(slow->next);
    slow->next = NULL;
    LinkList first = L->next;

    while (second != NULL) {
        LinkList nextFirst = first->next;
        LinkList nextSecond = second->next;
        first->next = second;
        second->next = nextFirst;
        first = nextFirst;
        second = nextSecond;
    }
}

先读辅助逆置函数：previous 是已逆置部分的首地址，current 是待处理地址。每轮先存 next；令 current 的 next 反指 previous；previous 改指 current，current 改指保存的 next。current 为空后，previous 就是新头，return 它。这个函数处理的是不带头结点的一段，因此别把 H 一起传入。

主函数前三个空检查覆盖无表、空表、单结点，不必重排。slow、fast 从首数据结点开始；只在 fast 后面还能走两步时推进，从而让 slow 停在前半末尾。second=reverseWithoutHead(slow->next) 接住逆置函数交回的新首；slow->next=NULL 使两段真正分开。

合并阶段 first 指前半当前，second 指后半当前。先保存两个旧后继，然后 first->next=second 把后半结点插入，second->next=nextFirst 接回前半后续，最后两个工作指针各转去事先存的后继。原后继一旦被改写，不能再从 first->next 读取“旧的下一个”。

4. 自己试：奇数多出的中间结点去哪了？

它保留在前半末尾，后半用尽后自然成为最后一个，不用另写插入。练习 1→2→3→4：分成 [1,2]、逆后半 [4,3]，结果 1→4→2→3。若忘记断链，旧箭头可能把结果接回已经插入的结点，形成环。

学懂后回看：结论、复杂度与回源

题意与结论：按首尾交替顺序重排原结点。三步：找中点、逆置后半段、把前半与逆序后半交替连接。

思路推导：每次从链头找尾结点并摘下，要反复扫描，最坏 O(n²)。把后半先反转，原来的“从后往前取”就变成普通顺序读取。

走一遍：1→2→3→4→5。快慢指针找到中点 3；后半 4→5 逆成 5→4，并把前半断成 1→2→3→NULL。取前半 1、后半 5、前半 2、后半 4，最后保留 3，结果 1→5→2→4→3。偶数长度 6 时是 [1,2,3] 与 [6,5,4] 交替。

代码抓手与正确性：slow 每次一步、fast 两步，前半长度不少于后半。逆置后必须 slow->next=NULL，否则可能留下旧连接形成环。交叉连接前先保存 nextFirst 和 nextSecond；修改 first/second 的 next 后，再靠保存的指针继续，不能沿已改写的边找原后继。

复杂度与易错点：三次线性处理合计 O(n)，空间 O(1)，不是 O(n³)。空链、单结点直接返回。奇数时中间结点留在前半末尾，自然最后出现，不需要再插一次。

回源：PDF 第 14 页；回源 · PDF 第 14 页 · b_14_0；PDF 第 14 页 · b_14_1 。正式代码

27｜单链表判环（本章第 12 题）

题目与要求

题目（依据原题整理）：单链表的某个结点如果把 next 指向前面已经经过的结点，沿链接行走就可能不断绕圈。编写算法，判断给定单链表是否有环。

已知条件：输入链表入口；普通无环链最终到达 NULL，有环链则会重复经过同一结点。

需要得到：有环返回 true，无环返回 false；本题不要求找到入环结点或计算环长。

输入 → 输出示例（教学补充）：1→2→3→NULL → false；若把结点 3 的 next 改为指向原结点 2，则 1→2→3→2→… → true。

约定与提醒（教学补充）：判断的是是否回到同一个结点地址，不是数据值是否重复。1→2→1→NULL 中两个 1 若是不同结点，仍然无环。

题干回源：Code59 PDF 第 14 页；回源 · PDF 第 14 页 · b_14_1 ，该块包含前题小结及本题。

1. 环是指箭头绕回去，不是数字重复

1→2→3→2结点 如果最后指向的是前面那个 2 的同一地址，就永远走不到 NULL，存在环。另一个正常链 [1,2,3,2] 的最后是新结点并指 NULL，即使值相同也无环。

slow 每轮一步，fast 每轮两步。正式函数从传入的 L 开始，本篇 L 指头结点 H。

2. 真正相遇的一次完整过程

图为 H→1→2→3→4→2，最后箭头回到原结点 2。

轮次	slow 走一步到	fast 连走两步的过程	是否同一地址
起始	H	H	此时不判断，尚未走
1	1	H→1→2	否
2	2	2→3→4	否
3	3	4→2→3	是，返回 true

为什么有环最终一定相遇？进入环后，快指针每轮相对多走一格，就像在圆形跑道上每轮追近一个位置；环有有限个位置，不可能永远错开。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool hasCycle(LinkList L) {
    LinkList slow = L;
    LinkList fast = L;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }

    return false;
}

两条初始化让指针先落在同一个起点。while 先检查 fast 存在、fast 的下一结点也存在，保证 fast->next->next 合法；再分别移动 slow 与 fast。移动之后才 slow==fast 判断，同地址即有环。

如果 while 因 fast 或其下一结点为空而退出，说明确实找到了链的末端，return false。这里没有 free，没有改任何结点 next，所以判定不会破坏原链。

4. 自己试与最常见错误

初始 slow==fast 只是因为你把它们放在同一个起点，不能因此直接返回有环。练习无环 H→1→2：第 1 轮 slow=1、fast=2；fast->next 为空，下轮不进，返回 false。想找环入口还需另一阶段，本题的相遇点 3 不一定是入口 2。

学懂后回看：结论、复杂度与回源

题意与结论：慢指针每次一步、快指针每次两步；移动后相遇说明有环，快指针能走到 NULL 则无环。

思路推导：用集合记录访问地址很直观，但要 O(n) 空间。环上快指针每轮比慢指针多走一步，相对距离模环长不断变化，最多经过一个环长的轮数就会追上。

走一遍：带头结点 H 的 H→1→2→3→4→2。按正式代码，起初两指针都在 H；第 1 轮慢到 1、快到 2；第 2 轮慢到 2、快经过 3 到 4；第 3 轮慢到 3、快经过 2 到 3，相遇，返回 true。无环 H→1→2→3→NULL 中，快指针最终无法再走两步。

代码抓手与正确性：循环条件为 fast!=NULL && fast->next!=NULL，然后才可读 fast->next->next。先移动再比较 slow==fast；正式代码初始都指向传入的 L（本篇约定为头结点），不能把初始相等误认为有环。从首数据结点开始也能判环，但手算相遇轮次会不同，不要混用。

复杂度与易错点：时间 O(n)，空间 O(1)，n 指可达不同结点数。比较地址，不比较 data；重复值不代表环。此题只判断有无环，不要求给出环入口，入口定位需要另外一步推导。

回源：PDF 第 14 页；回源 · PDF 第 14 页 · b_14_1 （此块同时含前题小结与本题内容）。正式代码