单链表算法题（二）：进阶技巧篇

单链表算法题（二）：进阶技巧篇

前言

在上一篇中，我们学习了链表题目的四大基本功：哨兵位、三指针反转、快慢指针找中点、归并合并。这些技巧足以应对大部分基础题目。

本篇将进入进阶领域，讲解三道更复杂的题目：

1. 链表分割— 分类重组的典型应用
2. 链表的回文结构— 综合运用多种技巧
3. 相交链表— 几何思维 + 双指针

这三道题的特点是：单一技巧无法解决，需要组合多种思路。掌握了它们，你的链表解题能力将再上一个台阶。

题目一：链表分割

牛客网 BM2. 链表分割

现有一链表的头指针pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

示例

输入：pHead = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 输入：pHead = [2,1], x = 2 输出：[1,2]

思路分析

题目要求：

1. 小于x的节点在前，大于等于x的节点在后
2. 各自的相对顺序不能改变

最直观的想法：创建两个链表，遍历原链表，根据条件分别插入两个链表，最后连接。

解法：双链表分离 + 重组

structListNode*partition(structListNode*pHead,intx){// 创建两个哨兵节点structListNode*lessHead=(structListNode*)malloc(sizeof(structListNode));structListNode*greaterHead=(structListNode*)malloc(sizeof(structListNode));structListNode*lessTail=lessHead;structListNode*greaterTail=greaterHead;structListNode*cur=pHead;while(cur!=NULL){if(cur->val<x){lessTail->next=cur;lessTail=lessTail->next;}else{greaterTail->next=cur;greaterTail=greaterTail->next;}cur=cur->next;}// ⚠️ 关键：防止成环！greaterTail->next=NULL;// 连接两个链表lessTail->next=greaterHead->next;structListNode*result=lessHead->next;free(lessHead);free(greaterHead);returnresult;}

为什么greaterTail->next = NULL至关重要？

看一个例子：

原链表: [1] → [4] → [3] → [2] → NULL, x = 3 如果不置空： 遍历结束后： less: [1] → [2] → NULL (lessTail = [2]) greater: [4] → [3] → NULL (greaterTail = [3]) 连接：lessTail->next = greaterHead->next 结果：[1] → [2] → [4] → [3] → NULL ✓ 看起来没问题？换个例子： 原链表: [1] → [4] → [2] → [3] → NULL, x = 3 遍历结束后： less: [1] → [2] → NULL (lessTail = [2]) greater: [4] → [3] → NULL (greaterTail = [3]) 连接：lessTail->next = greaterHead->next 结果：[1] → [2] → [4] → [3] → NULL ✓ 好像也没问题？再换个例子： 原链表: [1] → [4] → [3] → [2] → [5] → NULL, x = 3 遍历结束后： less: [1] → [2] → NULL (lessTail = [2]) greater: [4] → [3] → [5] → NULL (greaterTail = [5]) 连接：lessTail->next = greaterHead->next 结果：[1] → [2] → [4] → [3] → [5] → NULL ✓ 看起来都正确... 那为什么要置空呢？ 真正的问题出在：原链表中，greaterTail 的 next 可能还指向某个 less 节点！ 原链表: [1] → [4] → [3] → [2] → NULL, x = 3 遍历过程中，[2] 是 less 节点，它的 next 原本指向 NULL。 但如果 greaterTail 恰好指向 [4]，而 [4] 的 next 指向 [3]（也是 greater 节点）， 再连接 lessTail->next = greaterHead->next 时... 更典型的场景：如果最后一个节点被分到 less 链表， 那么 greaterTail 的 next 还指向这个被移走的节点，会导致成环！

实际例子（展示成环风险）：

原链表: [1] → [3] → [2] → NULL, x = 2 遍历： cur=1 (<2) → less: [1] cur=3 (>=2) → greater: [3] cur=2 (>=2) → greater: [3] → [2] greaterTail = [2] 此时 [2] 的 next 原本指向 NULL，没问题。 但如果原链表是：[1] → [3] → [2] → [4] → NULL, x = 2 遍历： cur=1 → less: [1] cur=3 → greater: [3] cur=2 → greater: [3] → [2] cur=4 → less: [1] → [4] lessTail = [4], greaterTail = [2] 不置空直接连接： lessTail->next = greaterHead->next [4] 的 next 指向 [3] 结果：[1] → [4] → [3] → [2] → [4] → ... ↑ ↓ └────────────┘ 成环了！！！ 因为 [2] 的 next 原本指向 [4]，而 [4] 现在被移到了 less 链表， 所以 [2]->next 还指向 [4]，形成了环！ 置空 greaterTail->next = NULL 后： [3] → [2] → NULL，断开连接，就不会成环了。

图解：

原链表: [1] → [3] → [2] → [4] → NULL, x = 2 分离后： less: [1] → [4] → NULL greater: [3] → [2] → [4] ← 还指向 [4]！ 置空 greaterTail->next： greater: [3] → [2] → NULL 连接： lessTail->next = greaterHead->next [1] → [4] → [3] → [2] → NULL ✓

复杂度：时间 O(N)，空间 O(1)

题目二：链表的回文结构

牛客网 BM3. 链表的回文结构

对于一个链表，请设计一个时间复杂度为 O(n)，额外空间复杂度为 O(1) 的算法，判断其是否为回文结构。

示例

输入：[1,2,2,1] 输出：true 输入：[1,2,3,2,1] 输出：true 输入：[1,2,3,4,5] 输出：false

思路分析

回文判断在数组上很容易（双指针从两端向中间逼近），但链表不支持从后往前遍历。

解决方案：反转后半部分链表，然后和前半部分比较。

解法：快慢指针 + 反转链表

// 反转链表（复用之前的函数）structListNode*reverseList(structListNode*head){structListNode*prev=NULL;structListNode*cur=head;structListNode*next=NULL;while(cur!=NULL){next=cur->next;cur->next=prev;prev=cur;cur=next;}returnprev;}boolisPalindrome(structListNode*head){if(head==NULL||head->next==NULL){returntrue;}// Step 1: 快慢指针找中点structListNode*slow=head;structListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}// Step 2: 反转后半部分structListNode*secondHalf=reverseList(slow);// Step 3: 比较structListNode*firstHalf=head;structListNode*second=secondHalf;while(second!=NULL){if(firstHalf->val!=second->val){returnfalse;}firstHalf=firstHalf->next;second=second->next;}returntrue;}

图解：

原链表: [1] → [2] → [3] → [2] → [1] → NULL Step 1: 快慢指针找中点 fast 走 2 步，slow 走 1 步 slow 到达 [3]（中间节点） Step 2: 反转后半部分 后半部分: [3] → [2] → [1] 反转后: [1] → [2] → [3] Step 3: 比较 前半部分: [1] → [2] → [3] 后半部分: [1] → [2] → [3] 完全匹配 ✓

边界情况

奇数长度: [1,2,3,2,1] slow 指向中间的 [3]，反转后半部分后： 前半部分: [1] → [2] → [3] 后半部分: [1] → [2] → [3]（中点和前半部分重合比较，不影响结果） 偶数长度: [1,2,2,1] slow 指向第二个 [2]（第二个中间节点），反转后半部分： 前半部分: [1] → [2] 后半部分: [1] → [2] 完美匹配 ✓

复杂度：时间 O(N)，空间 O(1)

💡注意：此题要求在 O(1) 空间下完成，所以不能使用数组或栈来存储。如果允许额外空间，可以把链表元素存入数组，然后用双指针判断。

题目三：相交链表

LeetCode 160. 相交链表

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。

示例

相交: A: [1] → [2] → [3] → [4] ↓ B: [5] → [6] → [4] 相交节点为 [4] 不相交: A: [1] → [2] → [3] B: [4] → [5] → [6]

思路分析

两个链表相交，意味着从某个节点开始，它们共享同一段内存（即同一个节点）。

解法一：双指针（浪漫相遇法）⭐

这是最优雅的解法，思路非常简单：

• 指针pA从headA出发，走完 A 链表后，转到headB继续走
• 指针pB从headB出发，走完 B 链表后，转到headA继续走
• 如果相交，它们一定会在相交点相遇
• 如果不相交，它们最终都会指向NULL

structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){if(headA==NULL||headB==NULL){returnNULL;}structListNode*pA=headA;structListNode*pB=headB;while(pA!=pB){pA=(pA==NULL)?headB:pA->next;pB=(pB==NULL)?headA:pB->next;}returnpA;}

为什么一定会相遇？

设 A 链表的非公共部分长度为a，B 链表的非公共部分长度为b，公共部分长度为c。

pA 走过的路程：a + c + b pB 走过的路程：b + c + a

两者相等！所以它们一定在相交点相遇。

图解：

A: [1] → [2] → [3] → [4] → [5] ↗ B: [6] → [7] → [8] pA 的路径: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 4 → 5 → 8 → 4 → 5 pB 的路径: 6 → 7 → 8 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 4 → 5 ↑ 在这里相遇！

不相交的情况：

A: [1] → [2] → [3] → NULL B: [4] → [5] → NULL pA: 1 → 2 → 3 → NULL → 4 → 5 → NULL pB: 4 → 5 → NULL → 1 → 2 → 3 → NULL ↑ 同时到达 NULL

复杂度：时间 O(m+n)，空间 O(1)

解法二：先求长度差

如果不理解上面的"浪漫相遇法"，可以先求长度差，再同步走：

structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){// 计算长度intlenA=0,lenB=0;structListNode*curA=headA;structListNode*curB=headB;while(curA){lenA++;curA=curA->next;}while(curB){lenB++;curB=curB->next;}// 让长的先走差值步curA=headA;curB=headB;intdiff=abs(lenA-lenB);if(lenA>lenB){while(diff--)curA=curA->next;}else{while(diff--)curB=curB->next;}// 一起走while(curA!=curB){curA=curA->next;curB=curB->next;}returncurA;}

复杂度：时间 O(m+n)，空间 O(1)

本讲总结

本篇的三道题目分别展示了不同的解题思路：

核心启示：

• 链表题目往往不是单一技巧能解决的，需要组合使用
• 指针操作时务必注意边界条件和成环风险
• 画图是解决链表问题的最好方法

思考题

1. 链表分割中，如果不置空greaterTail->next，在什么情况下会出问题？
2. 回文链表的解法中，反转后半部分后，原链表被破坏了。如果要求不能修改原链表，该怎么办？
3. 相交链表中，如果两个链表长度相差很大，哪种解法更好？

下一篇预告：[单链表算法题（三）：环与数学篇]，将讲解环形链表、环形链表 II，以及背后的数学证明。

如果你觉得这篇文章对你有帮助，欢迎点赞收藏！有问题请在评论区留言讨论。