143. 重排链表（中等）

Blind 75 › 143. 重排链表（中等） （第 4 章）
文章工具

题目

给定一个单链表的头节点 head，链表原本从左到右依次是 L0 → L1 → … → Ln-1 → Ln。

请把它改成首尾交替的样子：L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。

注意：必须在原链表上实际交换节点（改 next 指针），不能只是改节点里的 val。

自造示例：[10,20,30,40] → [10,40,20,30]；[7,5,9,3,1] → [7,1,5,3,9]。

约束：节点数 1 ~ 5 × 104；节点值 1 ~ 1000；函数应原地重排 head 指向的链表。

思路

一句话：先从中点把链表切成两半，再把后半段反转，最后与前半段交替拼接。

最直白的做法：先遍历一遍把节点存进数组，然后两个指针一个从最左、一个从最右，左右交替取出节点重新接起来。时间 O(n)，但额外空间 O(n)——单链表不能下标随机访问，必须先铺一层数组才能“从尾部取数”，不满足原地操作的目标。

关键观察：目标序列其实是两个序列的交错：

  • 前半段从头部正向取：L0, L1, L2, …
  • 后半段从尾部反向取：Ln, Ln-1, Ln-2, …

单链表的难点在“从尾部反向取”。但只要把后半段整体反转，反向取就变成了从新头节点正向取；于是左右两个子链都能用各自头节点简单交替拼接。

以 10 → 20 → 30 → 40 → 50 跟踪：

步骤链表状态
原始10 → 20 → 30 → 40 → 50
快慢指针找中点slow 停在 30，second 从 40 开始
断开first = 10 → 20 → 30；second = 40 → 50
反转后半段second = 50 → 40
交替合并10 → 50 → 20 → 40 → 30

因此选定「中点切开 + 反转后半段 + 交替合并」，全程只改指针，空间 O(1)。

解法

三步完成：

  1. 找中点并断开。 令 fast 从 head->next 出发、slow 从 head 出发；fast 一次走两步、slow 一次走一步。循环结束后前半段 first = head，后半段 second = slow->next，再令 slow->next 为 null 断开。
  2. 反转后半段。 用标准三指针 prev / cur / nxt 原地反转 second。
  3. 交替合并。 只要 second 非空，就保存双方后继，把当前 second 节点插到当前 first 节点之后，再双双推进。

下图把上面 3 个步骤串成流程，并逐步演示：

143. 重排链表（中等） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
143. 重排链表（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 void reorderList(ListNode* head) {
 if (!head || !head->next) {
 return;
 }  ListNode* slow = head;
 ListNode* fast = head->next;
 while (fast && fast->next) {
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。