单链表算法题二进阶技巧篇前言在上一篇中我们学习了链表题目的四大基本功哨兵位、三指针反转、快慢指针找中点、归并合并。这些技巧足以应对大部分基础题目。本篇将进入进阶领域讲解三道更复杂的题目链表分割— 分类重组的典型应用链表的回文结构— 综合运用多种技巧相交链表— 几何思维 双指针这三道题的特点是单一技巧无法解决需要组合多种思路。掌握了它们你的链表解题能力将再上一个台阶。题目一链表分割牛客网 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]思路分析题目要求小于x的节点在前大于等于x的节点在后各自的相对顺序不能改变最直观的想法创建两个链表遍历原链表根据条件分别插入两个链表最后连接。解法双链表分离 重组structListNode*partition(structListNode*pHead,intx){// 创建两个哨兵节点structListNode*lessHead(structListNode*)malloc(sizeof(structListNode));structListNode*greaterHead(structListNode*)malloc(sizeof(structListNode));structListNode*lessTaillessHead;structListNode*greaterTailgreaterHead;structListNode*curpHead;while(cur!NULL){if(cur-valx){lessTail-nextcur;lessTaillessTail-next;}else{greaterTail-nextcur;greaterTailgreaterTail-next;}curcur-next;}// ⚠️ 关键防止成环greaterTail-nextNULL;// 连接两个链表lessTail-nextgreaterHead-next;structListNode*resultlessHead-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 遍历 cur1 (2) → less: [1] cur3 (2) → greater: [3] cur2 (2) → greater: [3] → [2] greaterTail [2] 此时 [2] 的 next 原本指向 NULL没问题。 但如果原链表是[1] → [3] → [2] → [4] → NULL, x 2 遍历 cur1 → less: [1] cur3 → greater: [3] cur2 → greater: [3] → [2] cur4 → 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*prevNULL;structListNode*curhead;structListNode*nextNULL;while(cur!NULL){nextcur-next;cur-nextprev;prevcur;curnext;}returnprev;}boolisPalindrome(structListNode*head){if(headNULL||head-nextNULL){returntrue;}// Step 1: 快慢指针找中点structListNode*slowhead;structListNode*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;}// Step 2: 反转后半部分structListNode*secondHalfreverseList(slow);// Step 3: 比较structListNode*firstHalfhead;structListNode*secondsecondHalf;while(second!NULL){if(firstHalf-val!second-val){returnfalse;}firstHalffirstHalf-next;secondsecond-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继续走如果相交它们一定会在相交点相遇如果不相交它们最终都会指向NULLstructListNode*getIntersectionNode(structListNode*headA,structListNode*headB){if(headANULL||headBNULL){returnNULL;}structListNode*pAheadA;structListNode*pBheadB;while(pA!pB){pA(pANULL)?headB:pA-next;pB(pBNULL)?headA:pB-next;}returnpA;}为什么一定会相遇设 A 链表的非公共部分长度为aB 链表的非公共部分长度为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(mn)空间 O(1)解法二先求长度差如果不理解上面的浪漫相遇法可以先求长度差再同步走structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){// 计算长度intlenA0,lenB0;structListNode*curAheadA;structListNode*curBheadB;while(curA){lenA;curAcurA-next;}while(curB){lenB;curBcurB-next;}// 让长的先走差值步curAheadA;curBheadB;intdiffabs(lenA-lenB);if(lenAlenB){while(diff--)curAcurA-next;}else{while(diff--)curBcurB-next;}// 一起走while(curA!curB){curAcurA-next;curBcurB-next;}returncurA;}复杂度时间 O(mn)空间 O(1)本讲总结本篇的三道题目分别展示了不同的解题思路题目核心思路关键点链表分割分拆成两个链表再重组注意置空尾部防止成环回文链表找中点 反转 比较综合运用三种技巧相交链表双指针走完对方的路巧妙利用路程相等的原理核心启示链表题目往往不是单一技巧能解决的需要组合使用指针操作时务必注意边界条件和成环风险画图是解决链表问题的最好方法思考题链表分割中如果不置空greaterTail-next在什么情况下会出问题回文链表的解法中反转后半部分后原链表被破坏了。如果要求不能修改原链表该怎么办相交链表中如果两个链表长度相差很大哪种解法更好下一篇预告[单链表算法题三环与数学篇]将讲解环形链表、环形链表 II以及背后的数学证明。如果你觉得这篇文章对你有帮助欢迎点赞收藏有问题请在评论区留言讨论。
