企业官网建设流程全解析

昨天还在写链表的创建、遍历、插入、删除，觉得链表也就那么回事；今天刚开始练反转和判环，就被指针绕得有点晕。如果你也有同感，这篇笔记应该能帮上忙。第二天的主角是链表的进阶操作：单链表反转、快慢指针找中点、环形检测、删除倒数第N个结点、合并有序链表、判断相交，最后还要用这些操作组合起来解决回文判断。适合刚学完链表基础增删改查、准备进入刷题或面试阶段的读者。文章里的代码我用 C 写，核心是讲清楚每一次指针移动，换成 C++ 或 Python 思路完全一样。

1. 链表进阶到底在“进”什么：先建立操作坐标系

1.1 为什么第二天就上“进阶”

很多人学链表会卡在第一个反差上：基础操作都是顺着 next 走，逻辑非常直白；进阶操作却要让多个指针互相配合，甚至还要在递归里改指向。第二天练这些，不是因为基础不重要，而是因为链表的真正难点从来不是语法，而是“在内存里只能靠指针定位节点”这个抽象。你没法通过下标随机访问第 k 个节点，也没有现成的 length 函数，很多操作都必须从头遍历。进阶套路的价值，就是在这种限制下仍然做到 O(n) 时间、O(1) 额外空间。

还有一个更实际的原因：这些操作在工程里确实经常出现。像缓存淘汰、任务调度、编辑器撤销历史、链式哈希的冲突处理，底层多多少少都会涉及链表的反转、合并或环形检测。练一天基础，第二天上这些，时间线本身不算激进。把反转和快慢指针玩熟，后面学树、图、跳表的时候，你会发现自己对指针的掌控力完全不一样，很多看似新的结构也能很快迁移过去。

1.2 基础结点定义与几个辅助函数

为了避免每个例子都重复写环境代码，先把这一系列内容里会用到的基础结构定下来。下面这几段代码不复杂，但后面所有操作都会复用它们。单独把它们拎出来，是为了让反转、判环、合并这些函数看起来更干净，也方便你自己调试时直接复制。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int val; struct Node *next; } Node; Node *createNode(int val) { Node *p = (Node *)malloc(sizeof(Node)); p->val = val; p->next = NULL; return p; } void printList(Node *head) { while (head) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); } void freeList(Node *head) { Node *tmp; while (head) { tmp = head->next; free(head); head = tmp; } }

printList 和 freeList 在两个地方特别好用：一是手动构造测试用例后快速确认链表形状，二是写完操作函数后立刻打印结果，看节点顺序是否符合预期。这里不做复杂封装，是因为学习阶段把每一步摊开反而更容易理解。等这些操作都熟练了，再考虑封装成链表库也不迟。

1.3 复杂度思维：指针操作的本质是“定位”不是“搬运”

链表进阶操作有个共同规律：节点本身不搬，搬的全是指针。反转没有创建新节点，判环没有复制链表，删除倒数第N个也只改了一两个 next。由于每次定位一个节点都要从 head 开始走，所以绝大多数操作至少是 O(n)；只要能想清楚指针之间的关系，额外空间可以压到 O(1)。这也是面试里反复追问复杂度的地方，不是要你背 O(n)，而是看你能不能区分哪些遍历是必须的，哪些能通过双指针省掉。

下面这张表把第二天会碰到的操作按套路归了一下类。你会发现，很多题目根本不用死记代码，本质上就是快慢指针、反转、dummy node 这几个套路的组合。

2. 单链表反转：从“三指针”到递归，核心是别让后半段链表丢

2.1 迭代反转：三指针一次遍历

反转是链表进阶头号操作。思路说破也不复杂：从头开始遍历，把每个节点的 next 改成前一个节点。问题在于，你一旦改了 cur->next，原来 cur 后面的节点就找不到了，所以必须用一个临时指针先把下一个节点保存下来。这就是迭代反转里三个指针存在的意义：prev 指向前一个节点，cur 指向当前要改的节点，next 保存 cur 原本的下一个节点。

Node *reverseIter(Node *head) { Node *prev = NULL; Node *cur = head; Node *next = NULL; while (cur != NULL) { next = cur->next; // 先保存下一个节点 cur->next = prev; // 当前节点指向前一个 prev = cur; // prev 后移 cur = next; // cur 后移 } return prev; // 原链表最后一个节点变成新头 }

以 1->2->3->NULL 为例：第一轮先把 2 存到 next，然后让 1->NULL，prev 变成 1，cur 变成 2；第二轮让 2->1；第三轮让 3->2。最后 cur 到 NULL，prev 停在节点 3 上，返回 prev 就是反转后的新头。整个过程没有新建节点，没有复制数据，只是把每个节点的 next 掉了个头。

2.2 递归反转：让函数自己“翻”

递归版本的核心是先走到链表最后，再一层层往回改 next。很多人觉得递归难，是因为它把“先改指针”变成了“先到底，再回溯时改”。看代码时不要试图跟踪每一层，只需要相信：reverseRecur(head->next) 返回的是从下一个节点开始的、已经反转好的子链表。

Node *reverseRecur(Node *head) { if (head == NULL || head->next == NULL) { return head; } Node *newHead = reverseRecur(head->next); head->next->next = head; // 让下一个节点反过来指向自己 head->next = NULL; // 自己原来的 next 置空 return newHead; }

递归版本写起来很简洁，但代价是递归栈的深度等于链表长度。链表太长时容易栈溢出，所以工程代码里更常写迭代版本，递归版本更多用来考察对递归过程的理解。无论哪种写法，都要注意把 head->next 置空，否则反转后的链表尾部可能还残留一条指向旧位置的线，调试时就会遇到莫名其妙的环。

2.3 反转操作的边界条件与典型应用

反转最容易被忽略的是边界。空链表直接返回 NULL；只有一个节点时，迭代循环不进入，递归入口也直接返回 head。这两个边界恰好都被条件 cur != NULL 或 head->next == NULL 挡在了前面，所以写代码时不需要额外特判。

反转在实战里极少单独考，更多是作为子步骤出现。比如按 K 个一组反转链表，比如回文判断，再比如反转后半段来比较。把这些题目拆开看，你会发现核心都是“先整体会反转，再想清楚从哪个节点开始反转”。所以第二天的练习里，反转不只是背代码，而要真正能手写出来，并且说得清楚每一步在干什么。

3. 双指针家族：找中点、判环、倒数第N个结点一次讲清

3.1 快慢指针找中间结点

几乎所有双指针技巧，都是从找中间结点入门的。结论很直白：快指针每次走两步，慢指针每次走一步，当快指针到链表尾部时，慢指针恰好在中间。代码只有几行，但有两个细节值得单独说。

Node *findMiddle(Node *head) { if (head == NULL) { return NULL; } Node *slow = head; Node *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

第一个细节：如果链表长度是奇数，返回正中间结点；如果是偶数，返回第二个中间结点。比如 1->2->3->4，返回 3 而不是 2。很多回文、对折类题目默认要第二个中间结点，所以这个版本用起来最顺手。第二个细节：while 条件必须判断 fast != NULL 和 fast->next != NULL，因为 fast 一次跳两步，如果不检查 fast->next，下一步就可能访问空指针。

3.2 Floyd 判圈算法：为什么快慢指针一定会相遇

判环本质上是找中点的一个变种：同样用快慢指针，但这次不关心终点，只关心两者是否相遇。如果链表中没有环，fast 会先碰到 NULL，函数正常返回 false；如果有环，fast 会在环里一直转，slow 进入环后，两者之间的距离每次循环减少 1，最终必然相遇。这里的核心不是“快指针跑得比慢指针快”，而是相对速度是每轮 1 个节点，所以追及问题一定有解。

bool hasCycle(Node *head) { if (head == NULL || head->next == NULL) { return false; } Node *slow = head; Node *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }

写这段代码时最常犯的错误是 while 里只判断 fast != NULL。如果链表恰好没有环，循环最后 fast 会停在 NULL，下一轮再执行 fast->next->next 就直接崩溃。如果面试官进一步问环的入口，Floyd 算法还有第二阶段：相遇之后把 slow 重置到 head，然后两个指针都一次走一步，再次相遇的位置就是环入口。这个概念可以先记下来，作为后面拓展练习。

3.3 删除倒数第N个结点：一次遍历的偏移量技巧

删除倒数第 N 个结点，不用反转，也不用先遍历一遍求长度再走第二遍。办法是让两个指针拉开 N 个节点的距离，然后同步向后走：快指针先走 N 步，当快指针走到链尾时，慢指针的 next 正好指向要删除的节点。这里用 dummy 哨兵结点还有一个额外好处：删除头结点时不需要单独特判。

Node *removeNthFromEnd(Node *head, int n) { Node dummy; dummy.val = 0; dummy.next = head; Node *fast = &dummy; Node *slow = &dummy; while (n > 0 && fast != NULL) { fast = fast->next; n--; } while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next; } Node *toDelete = slow->next; slow->next = slow->next->next; free(toDelete); return dummy.next; }

为什么需要 dummy？因为 slow 要从 head 的前一个位置开始走。如果链表只有一个节点且 n=1，没有 dummy 的话，你会陷入“要删头结点但找不到它的前驱”的尴尬局面。有了 dummy，slow 指向 dummy，fast 先走一步到唯一节点，然后循环不进入，slow->next 正好就是要删除的头结点。处理完之后返回 dummy.next，新链表头就自动更新了。

4. 有序链表合并、相交检测、回文判断：组合拳怎么打

4.1 合并两条有序链表：dummy node 的妙处

合并两个有序链表是一道很经典的题，迭代版本的核心是 dummy node 加尾插法。每次从 l1 或 l2 里挑一个值更小的节点，接到 tail->next 上，然后移动对应链表的指针和 tail。整个过程没有创建新节点，只是把已有节点重新串起来。

Node *mergeTwoLists(Node *l1, Node *l2) { Node dummy; dummy.next = NULL; Node *tail = &dummy; while (l1 != NULL && l2 != NULL) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = (l1 != NULL) ? l1 : l2; return dummy.next; }

这里有个很重要的提醒：dummy 是栈上的局部变量，返回 dummy.next 完全没问题，但绝不能返回 &dummy，因为函数返回后栈空间就失效了。另外，当一个链表遍历完，另一个链表可能还有剩余节点，直接 tail->next = l1 ? l1 : l2 就能把剩余部分整体接上，不需要继续 while 循环。这个技巧在合并链表的同类题目里经常复用。

4.2 相交链表：先对齐长度，再双指针同步走

判断两个链表是否相交，最自然的办法是求长度然后对齐。为什么不能直接从两条链表的头部一起走？因为两条链表在相交之前长度可能不一样，相交之后的部分虽然长度一致，但起点错位，两个指针根本对不上。所以先让长链表走掉长度差，然后再同步比较。

int listLength(Node *head) { int len = 0; while (head != NULL) { len++; head = head->next; } return len; } Node *getIntersectionNode(Node *headA, Node *headB) { int lenA = listLength(headA); int lenB = listLength(headB); Node *pa = headA; Node *pb = headB; while (lenA > lenB) { pa = pa->next; lenA--; } while (lenB > lenA) { pb = pb->next; lenB--; } while (pa != NULL && pa != pb) { pa = pa->next; pb = pb->next; } return pa; }

如果两条链表确实相交，pa 和 pb 最终会在同一个节点相遇；如果没有相交，它们会一起走到 NULL，最终返回 NULL。这个方法的时间复杂度是 O(m+n)，额外空间 O(1)。另有一种不额外求长度的双指针交替遍历法，思路更巧妙，但理解成本更高，建议先把长度对齐这个版本写熟。

4.3 回文判断：快慢指针 + 反转的组合题

回文判断非常适合放在“第二天”的末尾，因为它把前面很多操作串起来了。思路是先用快慢指针找到后半段起点，再反转后半段，最后从原链表头和反转后的头同步比较。代码量不大，但每一行都在调用之前的“基本功”。

bool isPalindrome(Node *head) { if (head == NULL || head->next == NULL) { return true; } Node *slow = head; Node *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } Node *rev = reverseIter(slow); while (rev != NULL) { if (head->val != rev->val) { return false; } head = head->next; rev = rev->next; } return true; }

这个实现会修改原链表，所以在面试或竞赛里要确认是否允许修改输入。如果要求不改变原链表，一种常见做法是借助栈保存前半段节点，再与后半段比较；或者复制一份链表再反转，不过额外空间会变成 O(n)。从进阶角度讲，能想到把“找中点”和“反转”组合起来，比单独背一个回文判断代码更有价值。

5. 链表进阶操作的坑与调试实录：从崩溃到死循环

5.1 空指针解引用：十个链表 bug 九个在这

链表题最经典的崩溃，是把空指针的 next 拿来赋值。常见场景包括：while 循环里没判 fast && fast->next 就访问 fast->next->next；删除节点时先写 slow->next = slow->next->next，但没确认 slow->next 不是 NULL；递归反转时没有处理空链表入口。我的调试习惯是每写一个 while，先问自己一句：这个循环最后停在哪里？如果停在 NULL 上，那循环体里能安全访问的指针有哪些？把这个问题想清楚，大部分空指针问题可以在代码写出来之前就消灭掉。

5.2 反转里的顺序错误和递归尾部残留

反转三指针的代码很容易把顺序写错。假如你先写 cur->next = prev，再写 next = cur->next，那 next 拿到的已经不是原来的下一个节点了，后半截链表直接丢失。正确的顺序永远是先用 next 保存 cur->next，再修改 cur->next，最后整体移动。这个顺序不是代码风格问题，是正确性问题。

递归反转也有一个常见错误：改完 head->next->next = head 之后，忘记把 head->next 置为 NULL。这会让链表的最后一个节点仍然指向它的前一个节点，打印或遍历时可能出现死循环。排查这类问题时，建议直接把链表打印出来，如果看到 1 -> 2 -> 3 -> 2 -> 3 这种重复序列，基本就是尾部没有断环。

5.3 边界测试法：1 个结点、2 个结点、空链表

链表进阶操作靠“看起来对”是不够的，边界测试必须做深。我建议每个操作都至少跑下面四个用例：

比如反转 1->2，正确结果是 2->1，如果结果还是 1->2，大概率是指针移动顺序写错。删除倒数第 1 个节点时，用 1->2->3 测试，正确结果是 1->2。这类小用例看起来简单，但能把大部分逻辑错误挡在提交之前。测试时可以配合 createNode 手动构造链表，再用 printList 在每个关键步骤后打印，观察形状变化。

5.4 写链表代码的几个个人习惯

最后分享几个我自己写链表代码时的习惯。第一，先画再写，尤其是反转、相交这种跨步操作，在纸上画一张图往往比盯着屏幕半天下结论要快得多。第二，用最短的链表验证核心逻辑，比如 1->2->3->4，每执行一步就用 printList 看结果。第三，写删除相关函数时，先决定哪些节点会被回收，记得调用 free，避免多次运行后出现内存泄漏。第四，如果函数会修改输入链表，在注释里明确写出来，避免调用者以为原链表还能继续使用。

我第二天练下来最大的感受是，链表进阶操作没有一个需要死记硬背。反转就是把 next 先保存下来再改；快慢指针就是用相对速度解决定位问题；dummy node 是为了把边界情况变成普通情况。真正难的不是代码，是动手前有没有把指针关系画明白。只要这个习惯养成了，后面再遇到更复杂的数据结构，你会比别人稳很多。