周口市网站建设_网站建设公司_留言板_seo优化

场景想象：

你手中有长长的一条纸带：1 -> 2 -> 3 -> 4 -> 5。

题目要求你把它变成：1 -> 5 -> 2 -> 4 -> 3。

这看起来像是把纸带对折，然后像拉链一样把两边的节点交替穿插在一起。

解题策略（拆解为三步）：

1. 找中点：把链表从中间切开，分成左右两半。

   • 左半段：1 -> 2 -> 3

   • 右半段：4 -> 5

2. 反转右半段：把右边的链表逆序。

   • 右半段变身：5 -> 4

3. 合并链表：左边取一个，右边取一个，像拉链一样缝合。

   • 1连5，5连2，2连4...

力扣 143. 重排链表

https://leetcode.cn/problems/reorder-list/

题目分析：

• 输入：链表头head。

• 目标：按 $L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to \dots$ 的顺序重排。

• 要求：原地操作，不能改变节点内部的值，只能改指针。

核心思维：快慢指针 + 反转 + 归并

这道题没有新知识，全是旧知识的排列组合。

1. 找中点：使用快慢指针（参考 LC 876）。

   • slow走一步，fast走两步。当fast到头时，slow就在中间。

2. 反转：使用双指针迭代（参考 LC 206）。

   • 把后半段链表反转过来，方便我们从尾部开始拿节点。

3. 合并：双指针交替连接。

   • l1指向左半段头，l2指向右半段头。

   • 暂存l1.next和l2.next，然后l1 -> l2 -> l1_old_next。

代码实现 (JavaScript)

JavaScript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */ var reorderList = function(head) { if (!head) return; // --- 第一步：找中点 (快慢指针) --- let slow = head; let fast = head; // 注意条件：我们要让 slow 停在中间节点（如果是偶数个，停在前半段的最后一个） while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; } // slow 现在是中点。 // 把链表切断！这一步很重要，否则后面会死循环 let rightHead = slow.next; slow.next = null; // --- 第二步：反转后半段 (标准反转模板) --- let pre = null; let cur = rightHead; while (cur !== null) { let temp = cur.next; cur.next = pre; pre = cur; cur = temp; } // 反转后，pre 就是右半段的新头结点 let l1 = head; // 左半段头 let l2 = pre; // 右半段头 // --- 第三步：合并两个链表 (拉链法) --- // 因为左半段总是 >= 右半段长度，所以只要 l2 还有节点就要继续 while (l1 !== null && l2 !== null) { // 1. 先把两边原本的“下一步”存起来，防止断链 let l1_next = l1.next; let l2_next = l2.next; // 2. 连线：左 -> 右 l1.next = l2; // 3. 连线：右 -> 左的下一步 l2.next = l1_next; // 4. 指针推移，准备处理下一对 l1 = l1_next; l2 = l2_next; } };

深度模拟

假设1 -> 2 -> 3 -> 4 -> 5

Step 1: 找中点

• fast走两步到 3，slow到 2。

• fast走两步到 5，slow到 3。

• fast再走就要越界了，停。

• slow在 3。

• 切断：左边1->2->3->null，右边4->5。

Step 2: 反转右边

• 4->5变成5->4。1

• 此时l1 = 1,l2 = 5。2

Step 3: 合并3

• Round 1:4

  • 存路：l1_next = 2,l2_next = 4。5

  • 连线：1 -> 5，5 -> 2。6

  • 链表变：1 -> 5 -> 2...

  • 移步：l1到 2,l2到 4。7

• Round 2:8

  • 存路：l1_next = 3,l2_next = null。9

  • 连线：2 -> 4，4 -> 3。

  • 链表变：1 -> 5 -> 2 -> 4 -> 3...

  • 移步：l1到 3,l2到 null。

• End:l2为空，结束。

总结

这道题虽然代码长，但逻辑非常清晰。它其实就是：

LC 876 (找中点) + LC 206 (反转) + 链表拼接。

• 易错点：找完中点后，一定要记得slow.next = null断开链表！否则左半段的尾巴还连着右半段，反转后会形成环，导致死循环。

下一题预告：K 个一组翻转链表

恭喜你拿下了综合题！下一题是 LC 25. K 个一组翻转链表（专题八）。

这是链表题里的 Hard 难度，也是字节跳动等大厂面试官最喜欢用来“劝退”或者“定级”的题目。

• 题目：1->2->3->4->5，K=2。

• 结果：2->1->4->3->5。

• 如果是 K=3：3->2->1->4->5。

这道题是对指针操作精细度的终极考验。准备好迎接这个 Boss 了吗？😎