企业官网建设流程全解析

链表OJ，四个字足够让刚学完链表概念的人心里发怵。数组题做多了，大脑会默认“有下标万事大吉”，而链表里节点全靠指针串在一起，查一个节点要遍历一遍，删一个节点要先记住前驱，稍不留神就解引用了空指针，代码直接崩溃。这篇笔记是对“链表OJ”这个专题做的完整归纳，我会把初阶阶段出现频率最高的十道题一次讲完：移除链表元素、反转链表、链表的中间结点、倒数第k个结点、合并两个有序链表、链表分割、回文链表，以及环形链表判定、找环入口、链表相交。每道题都会给出完整可跑的代码，并把思路、复杂度、坑点交代清楚。适合刚学完链表准备刷题的同学，也适合期末复习或者求职面试前快速过一遍的人。

1. 链表OJ到底在考什么

先把话说明白：链表题考的不是“你会不会遍历链表”，而是三个能力。

第一是指针操作。链表的增删改查本质上就是改指针的指向。你觉得逻辑全对，代码写出来却总是“差点意思”，多半是改变指向的顺序出了问题。最典型的例子就是反转链表，三行代码里有一条赋值顺序不对，结果就完全不一样。

第二是边界条件。链表题最容易翻车的地方不是核心思路，而是各种边界：空链表、只有一个节点、删除头节点、k的值比链表长度还大、偶数个节点找中间位置……这些情况稍微漏一个，OJ上就会显示答案错误，或者运行时直接崩溃（segment fault）。

第三是内存管理。用C写链表题，malloc出来的节点要用free还回去。至少三种情况会被判错：忘了释放被删除的节点、忘了释放临时的dummy节点、在大量测试用例下内存越界。OJ系统是无情的，本地跑得好不代表提交能过，因为很多问题只有在严格的评测环境下才会暴露出来。

这里还要强调一个认知：链表题在逻辑上往往比数组题简单，但代码上的出错率高得多。数组题的bug大多是“算错下标”，链表题的bug则集中在“空指针解引用”和“while死循环”两类。你心里装着这个分类，调试的时候就能快速缩小范围。

2. 开写之前，先建立两个底层思维

这两个思维贯穿后面所有题目，我先单独拿出来讲清楚。

2.1 虚拟头节点：把删头节点变得和其他位置一样

在链表里删除节点，很多人的第一版代码长这样：如果要删的是头节点，直接head = head->next；如果要删的是中间节点，要先找到前驱 prev，再prev->next = cur->next。你会发现头节点和中间节点要分开写，if 套 if，代码又长又容易漏。

解决办法就是虚拟头节点（dummy node）。自己malloc一个不存有效数据的节点，让它的 next 指向真正的头节点。这样原链表里每个节点都有前驱了，删除逻辑可以统一写成：

prev->next = target->next;

不用再单独判断“是不是头节点”，代码量直接砍掉一半。这里有两个容易被忽略的细节：

• 用C写的时候，dummy是malloc出来的，函数结束前记得free掉，否则每次调用都会泄漏一点内存，大量测试用例跑下来就会累积成越界错误。
• 返回的是dummy->next，而不是原来那个head变量。因为head可能已经被删了，你手头那个栈变量早就不是有效头节点了。

2.2 快慢双指针：一次遍历解决一半问题

链表没有随机访问能力，想拿到“中间位置”“倒数第k个”“是否存在环”这类信息，最优雅的办法是快慢双指针。

所谓快慢指针，就是两个指针同时从头出发，快指针每次走两步（fast = fast->next->next），慢指针每次走一步（slow = slow->next）。快指针走到末尾时，慢指针恰好停在链表的中部，所以找中间节点、判断回文、检测环形链表全都靠它。

找倒数第k个节点则换一种玩法：先让快指针走k步，然后两个指针同步前进，快指针到末尾时，慢指针的位置正好是倒数第k个。

快慢指针的正确性来自步数差，但真正要记住的是 while 循环的条件：

while (fast && fast->next)

必须同时判断fast本身和fast->next不为空，否则快指针走两步时会对空指针解引用，程序秒崩。这几乎是所有快慢指针题统一的标准写法，背熟它。

2.3 动手前先列边界条件

我的习惯是：不管题目多简单，下笔之前先在草稿纸上写几行字：空链表、单节点、双节点。再把题目语言翻译成具体边界，比如：

• 删除元素题：元素在头部、在中间、在尾部、值根本不存在。
• 倒数第k个：k等于链表长度、k比链表长度大。
• 中间节点：节点数为奇数、节点数为偶数。

OJ题的大部分扣分点其实不在核心算法上，而在这些边角料里。你愿意花两分钟把情况列清楚，后面写代码就会自然带上保护判断，而不是写完再回头补。这个问题想明白了，刷题效率能提升一倍。

3. 七道入门必刷题逐题拆解

下面这七道题，难度从一颗星到三颗星，按我推荐的顺序刷下来，链表的基本功就稳了。每道题我都先讲思路，再给代码，最后说坑。

3.1 移除链表元素

题目要求：删除链表中所有值等于给定 val 的节点，返回新链表的头节点。这是虚拟头节点最典型的应用场景。

思路：用一个 prev 指针遍历，每次检查prev->next的值是否需要删除。如果是，把prev->next指向待删节点的 next，并 free 掉待删节点；如果不是，prev 正常前进。

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; struct ListNode* prev = dummy; while (prev->next) { if (prev->next->val == val) { struct ListNode* toDelete = prev->next; prev->next = toDelete->next; free(toDelete); } else { prev = prev->next; } } struct ListNode* newHead = dummy->next; free(dummy); return newHead; }

时间复杂度O(n)，空间复杂度O(1)。注意我free的是待删除的节点，而不是prev。很多初学者图省事写成prev->next = prev->next->next，功能没错，但被跳过的节点没有free，在C的OJ评测里会被判为内存泄漏。

3.2 反转链表

题目要求：把整条链表反序，返回新的头节点。核心是三个指针的配合：prev记录前驱，cur记录当前节点，next先保存cur的下一个节点。

为什么必须先把 next 存下来？因为一旦执行cur->next = prev，cur 原来指向的后半段链表就找不到了。所以顺序必须是：先保存后面的节点，再改当前指向，最后整体平移。

struct ListNode* reverseList(struct ListNode* head){ struct ListNode* prev = NULL; struct ListNode* cur = head; while (cur) { struct ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

这是链表题里出的最多的一道，没有之一。面试官经常在此基础上变形：反转前n个节点、反转链表中的一段、每k个一组反转。原理全是这一套三指针平移，先把基础版想透，再说变形。

3.3 链表的中间结点

题目要求：给定头节点，返回链表的中间节点。偶数个节点时返回第二个中间节点（比如长度为4，返回第3个节点）。快慢指针一次遍历就能拿到：

struct ListNode* middleNode(struct ListNode* head){ struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }

这个 while 条件要特别记牢：fast->next必须一起判断。当链表中只有一个节点时，fast->next是 NULL，如果不判断，下一轮访问fast->next->next就变成了对空指针解引用。复杂度O(n)时间O(1)空间。顺便说一句，这个函数是后面回文链表题的前置操作。

3.4 链表中倒数第k个结点

经典题。思路是双指针拉开距离：快指针先走k步，然后两个指针同步前进，快指针到末尾时，慢指针正好指向倒数第k个节点。

struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode* fast = head; struct ListNode* slow = head; while (k--) { if (fast == NULL) return NULL; fast = fast->next; } while (fast) { fast = fast->next; slow = slow->next; } return slow; }

最容易踩的坑是 k 大于链表长度。快指针还没走完k步就遇到了 NULL，此时必须直接返回 NULL，否则下一轮会对空指针解引用。另一种标答是先遍历一遍数出长度 n，再走 n-k 步，思路更直观但要遍历两次；双指针版只遍历一次，更接近面试官想听到的答案。

3.5 合并两个有序链表

题目要求：把两个升序链表合并成一个新的升序链表。用 dummy 节点加一个 cur 游标，每次把值更小的节点接到 cur 后面。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; struct ListNode* newHead = dummy->next; free(dummy); return newHead; }

核心技巧在收尾那一行cur->next = l1 ? l1 : l2。当某个链表走空了，另一个链表剩余部分直接整段接上，不需要一个节点一个节点地遍历。这比很多人习惯的“再把剩余节点while循环接上”要简洁得多，而且不容易漏。原地合并，空间O(1)，时间O(n+m)。

3.6 链表分割

题目描述：给定一个链表和一个值 x，把所有小于 x 的节点排在大于等于 x 的节点之前，且保持原来的相对顺序不变。

思路：把原链表拆成两条临时链表，一条收集小于 x 的节点，一条收集大于等于 x 的节点，最后把两条接起来。每条临时链表都带一个 dummy 节点方便操作。

struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* lessDummy = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterDummy = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* less = lessDummy; struct ListNode* greater = greaterDummy; struct ListNode* cur = head; while (cur) { if (cur->val < x) { less->next = cur; less = less->next; } else { greater->next = cur; greater = greater->next; } cur = cur->next; } greater->next = NULL; less->next = greaterDummy->next; struct ListNode* newHead = lessDummy->next; free(lessDummy); free(greaterDummy); return newHead; }

这里的关键坑点在于：大值链表的尾节点的 next 一定要置为 NULL。否则它可能还指向小值链表末尾的某个节点，两条链表一接，直接形成一个环，提交上去就会超时，评测系统判断为死循环。这个题是面试常考的，因为它考察的不只是能不能写出代码，更考察你有没有意识到成环问题。

3.7 链表的回文结构

判断一个链表是不是回文：正着读和反着读一样。比如 1->2->3->2->1 是回文，1->2->2->1 也是。用数组收集所有值再判断，当然能做，但面试通常要求空间O(1)。

三步走：

1. 用快慢指针找中间节点；
2. 反转后半段链表；
3. 从两端同时向中间遍历比较，只要有一处不同就不是回文。

bool isPalindrome(struct ListNode* head){ if (!head || !head->next) return true; struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } struct ListNode* prev = NULL; struct ListNode* cur = slow; while (cur) { struct ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } struct ListNode* left = head; struct ListNode* right = prev; while (right) { if (left->val != right->val) return false; left = left->next; right = right->next; } return true; }

这里用 right 作为循环终止条件，而不是 left。原因是反转后半段之后，后半段是从原来的后半段头一路指回中间的，right 这条链的终点是 NULL，而 left 这一侧可能还比 right 多一个节点（奇数长度场景）。如果以 left 为准，就会访问到反转区之外，越界。如果面试官要求不改动原链表，比较完把后半段再反转一次接回去即可。

4. 两道进阶题：环形链表与相交链表

入门七道题做完，再上两道“准进阶”题。它们在逻辑上绕一个弯，但用的还是底层思维。

4.1 判断单链表是否带环

经典题。用快慢指针，如果有环，快指针会先进入环并在环里转圈，慢指针进入环后两者最终一定会在某个节点相遇。依赖一个朴素的事实：在环内，快指针相对于慢指针每次多走一步，所以不可能永远错过。

bool hasCycle(struct ListNode *head){ struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; }

输入链表可能是带环的，如果 while 条件写错就可能在环里无限循环，OJ 直接报超时。另外一个容易被问到的细节：为什么快指针一定能追上慢指针？因为在环内，两指针的距离差每次减1，环长有限，最多走不到一圈就能追上，不存在“跳过去”的可能。

4.2 找到环的入口节点

在判断有环的基础上再找环的入口，这才是环形链表的完整考法。

先推导。设头节点到环入口的距离为 a，环入口到相遇点的距离为 b，相遇点继续走到环入口的距离为 c，环长 L = b + c。慢指针走的路程是 a + b，快指针走的路程是 a + b + nL。快指针速度是慢指针的两倍，所以：

a + b + nL = 2(a + b) → a + b = nL → a = nL - b

当 n = 1 时，a = L - b = c。也就是说：从头节点出发的指针，和从相遇点出发的指针，各自每次走一步，最终会在环入口相遇。n 大于1的情况，等价于在环里多绕几圈，结论不变。

struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (fast == NULL || fast->next == NULL) return NULL; struct ListNode* ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; }

网上很多人只记住了“相遇后从头走一个指针，再相遇就是入口”，却说不清为什么。面试时把这个等式写出来，立刻就能和背答案的人拉开差距。

4.3 求两个链表的第一个相交节点

两个单链表相交，是指它们从某个节点开始共用同一批节点，形状像字母Y。题目要求返回第一个相交节点。

最直接的方法是算长度差：分别遍历两个链表得到长度 n1、n2，长链表先走 |n1-n2| 步，然后两个指针同步走，第一个相等的位置就是交点。更简洁的写法是双指针交替走：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (headA == NULL || headB == NULL) return NULL; struct ListNode* pa = headA; struct ListNode* pb = headB; while (pa != pb) { pa = pa ? pa->next : headB; pb = pb ? pb->next : headA; } return pa; }

为什么可行？两个指针都相当于走了链表A加链表B的总长度。两条链表相交时，pa 和 pb 会在某一步同时到达交点；不相交时，它们最后会同时走到 NULL，循环自然结束。网上常把这个叫“换头走法”，本质上是把两条链表的长度差抹平了。

5. 链表调试实战：从崩溃到AC

算法题写出来只是第一步，真正花时间的是调试。链表题的调试有自己的套路，和普通程序不太一样。

5.1 画图是你最好的调试工具

链表题最忌讳空想。我在本地跑每道题之前，一定先在草稿纸上画一个三节点的链表，把每个节点的地址和值写出来，再手动模拟指针的变化。画着画着就能发现很多隐藏问题，反转链表里的赋值顺序、链表分割里尾节点是否置空，这些都是画图能一眼看出来的。

一个实用的辅助函数，在本地测试时打印链表内容：

void printList(struct ListNode* head){ int count = 0; while (head && count < 20) { printf("%p:%d -> ", head, head->val); head = head->next; count++; } printf("NULL\n"); }

count 上限的作用是防止死循环链表把控制台刷爆，调试环形链表时尤其有用。建议把它放进你的常用代码片段里，每道题本地测试都先跑一遍。

5.2 必测的六组用例

每次交代码前，至少要把下面六组用例在本地过一遍：

• 空链表：head 为 NULL，函数不崩且返回合理值。
• 单节点链表：很多 while 条件的问题在这里暴露。
• 双节点链表：偶数长度场景，检查 fast->next 的边界。
• 值全部相同：删除题里所有节点都被删光，应返回 NULL。
• 极端参数：k 大于链表长度、x 比所有节点值都小或都大。
• 长链表压力测试：构造 5000 个节点的用例，验证时间和内存。

5.3 常见崩溃与超时的定位方法

• 段错误（Segmentation fault）：十有八九是对 NULL 解引用。在可疑语句前加 printf 打印指针，或者用调试断点看崩在哪一行，再检查那一行访问了哪个指针。
• 超时（Time Limit Exceeded）：链表题超时基本都是死循环。检查 while 条件是否保证了每一步都让指针向内移动，特别留意快指针走两步之前是否判断了 fast->next。
• 答案错误：先把返回头节点的逻辑重新看一遍。很多链表题会改动原链表，头节点可能已经变化，这时候返回 dummy->next 是最稳的。

6. 高频报错与避坑速查表

把常见问题整理成一张表，建议截图保存，每次提交前对照自查：

三条血泪经验，是我自己踩过无数次坑之后总结的：

• 写完代码，先把所有“->”扫一遍，凡是可能为 NULL 的地方优先补保护。
• 涉及节点删除或反转时，先保存即将丢失的指针，再改变指向，顺序永远不能反。
• 提交前，在一个最小用例上手动模拟一遍完整流程，不要写完直接交。

我个人的体会是：链表OJ考验的其实不是智商，而是你有没有养成“边界优先、画图先行”的习惯。一开始我总急着看答案，后来耐下性子，每道题先画图再手写，正确率明显上来了。把这组题目吃透之后，后面学树的遍历、图的邻接表，你会发现很多操作本质上还是链表那套指针思维。刷题平台上的题目外观再怎么变，底层其实就是三件事：虚拟头节点、快慢双指针、边界条件。把这三件小事磨利了，链表OJ这座山，你就稳稳当当地翻过去了。