LeetCode 143中等链表

重排链表图解题解

一条链表，把头尾交替穿插重排——快慢找中点、反转后半、交替合并，全程不借额外空间。

重排链表分三步：快慢指针找中点（fast 跑两格、slow 跑一格，fast 到头时 slow 停在正中间），从中点把链表劈成两截，把后半段用三个指针 prev/cur/nxt 逐个掉头反转，最后从前半和反转后的后半各取一个节点、交替接在一起——你一个我一个，把 next 指针一根根接好，直到两截都接完。

这道题到底在问什么

给定单链表 L0→L1→…→Ln，原地重排为 L0→Ln→L1→Ln-1→L2→Ln-2→…，不改节点值、只改指针。

输入: 1→2→3→4→5→6
输出: 1→6→2→5→3→4
输入: 1→2→3→4→5
输出: 1→5→2→4→3

最优解：一步一步想明白

3记住这三步：找中点 → 反转后半 → 交替合并。下面逐帧看清每一步指针怎么动。
4找中点用快慢指针：slow 一次走 1 格、fast 一次走 2 格，都从头出发。fast 到尽头时，slow 正好停在中点。
5第 1 轮：slow 先稳稳走 1 格到下标 1。接着看 fast 跨两格——拆两小跳看清楚。
6fast 的第一小跳：跨到下标 1。
7fast 的第二小跳：再跨到下标 2。slow 走 1、fast 走 2 的 2 倍速，让 fast 到头时 slow 恰好在中点。
8第 2 轮：slow 先稳稳走 1 格到下标 2。接着看 fast 跨两格——拆两小跳看清楚。
9fast 的第一小跳：跨到下标 3。
10fast 的第二小跳：再跨到下标 4。slow 走 1、fast 走 2 的 2 倍速，让 fast 到头时 slow 恰好在中点。
11fast 走到链表最后一个节点（下标 5），无法再跨两格，找中点结束。此刻 slow 停在下标 3，正是正中间。
12劈分完成：前半是下标 0…2（绿色，共 3 个），后半是下标 3…5（共 3 个）。slow 指向后半的第一个，下一步把后半整段反转。
13先把前半和后半断开：前半最后一个（下标 2）的 next 置空（中间那根连线变 ·）。cur 从后半头下标 3 起步，prev 初始为空。
14掉头前先存好后继：nxt = cur.next = 下标 4。不先存，掉头后就找不到下一个了（链表题最常见的丢 next 坑）。
15掉头前先存好后继：nxt = cur.next = 下标 5。不先存，掉头后就找不到下一个了（链表题最常见的丢 next 坑）。
16把 cur(下标 4) 的箭头掉头指向 prev(下标 3)：那根连线变 ←。后半段被一节一节翻过来。
17cur 在下标 5，它是后半最后一个，nxt 为空。
18把 cur(下标 5) 的箭头掉头指向 prev(下标 4)：那根连线变 ←。后半段被一节一节翻过来。
19后半反转完成：head2 落在下标 5（原来的最后一个 6），它是反转后半的新头。现在前半 1→2→3、反转后半 6→5→4，准备交替合并。
20把链表摆成两行：上「前半 1→2→3」、中「反转后半 6→5→4」，下面是空的结果行。head1 指前半头、head2 指后半头，从前半先取。
21轮到取前半：head1 指向 1（下标 0），把它接到结果尾。
22把 1 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
23轮到取后半：head2 指向 6（下标 0），把它接到结果尾。前后交替是重排的关键。
24把 6 接到结果尾（变绿），后半取走的节点标灰、指针前移。下一节轮到取前半。
25轮到取前半：head1 指向 2（下标 1），把它接到结果尾。
26把 2 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
27轮到取后半：head2 指向 5（下标 1），把它接到结果尾。前后交替是重排的关键。
28把 5 接到结果尾（变绿），后半取走的节点标灰、指针前移。下一节轮到取前半。
29轮到取前半：head1 指向 3（下标 2），把它接到结果尾。
30把 3 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
31轮到取后半：head2 指向 4（下标 2），把它接到结果尾。前后交替是重排的关键。
32把 4 接到结果尾（变绿），后半取走的节点标灰、指针前移。两半都取完，重排结束。
33两半接完，结果 1→6→2→5→3→4。回头核一遍：第 1 位 1 来自前半头。
34第 2 位 6 来自后半（从尾往回），前后交替无误。
35第 3 位 2 来自前半，前后交替无误。
36第 4 位 5 来自后半（从尾往回），前后交替无误。
37第 5 位 3 来自前半，前后交替无误。
38最后一位 4。整条 1→6→2→5→3→4 正是 L0→Ln→L1→Ln-1→… 的头尾交替，重排正确。

⚠️ 容易写错的地方

✗ 错：反转后半时直接改 next

✓ 对：先 nxt = cur.next 存好后继再掉头

不先存，掉头后整条后半就断了，找不到下一个

✗ 错：忘了断开前后两半

✓ 对：slow.next = null 先断开

不断开，合并时会绕回前半形成环，死循环

✗ 错：合并时丢失下一个节点

✓ 对：先把 first.next / second.next 都存到 n1 / n2 再改指针

改了 first.next 就找不到前半的下一个了

完整代码（Python / Java / JavaScript / C++）

Python

def reorderList(head):
    if not head or not head.next: return
    # ① 快慢找中点
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # ② 反转后半（从 slow.next 起）
    second = slow.next
    slow.next = None      # 断开前后两半
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    # ③ 前后交替合并
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

Java

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        // ① 快慢找中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // ② 反转后半（从 slow.next 起）
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode nxt = second.next;
            second.next = prev;
            prev = second;
            second = nxt;
        }
        // ③ 前后交替合并
        ListNode first = head;
        second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1; second = n2;
        }
    }
}

JavaScript

function reorderList(head) {
  if (!head || !head.next) return;
  // ① 快慢找中点
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // ② 反转后半（从 slow.next 起）
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second) {
    const nxt = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  // ③ 前后交替合并
  let first = head;
  second = prev;
  while (second) {
    const n1 = first.next, n2 = second.next;
    first.next = second;
    second.next = n1;
    first = n1; second = n2;
  }
}

C++

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    // ① 快慢找中点
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // ② 反转后半（从 slow->next 起）
    ListNode* second = slow->next;
    slow->next = nullptr;
    ListNode* prev = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev;
        prev = second;
        second = nxt;
    }
    // ③ 前后交替合并
    ListNode* first = head;
    second = prev;
    while (second) {
        ListNode* n1 = first->next;
        ListNode* n2 = second->next;
        first->next = second;
        second->next = n1;
        first = n1; second = n2;
    }
}

复杂度

时间

O(n)

找中点走半条 + 反转半条 + 合并半条，都是线性

空间

O(1)

原地反转后半 + 原地接线，只用常数个指针，不新建节点

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着重排链表的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么用 fast.next && fast.next.next 而不是 fast && fast.next？+

前者让 slow 停在前半最后一个（偶数时偏前），slow.next 才是后半头，劈分更干净；后者会让 slow 偏到后半。

能不能不反转、用栈做？+

可以：把后半压栈，再前半逐个与栈顶交替接。但栈是 O(n) 空间，不满足进阶的 O(1)。

合并循环用 while(second) 还是 while(first)？+

反转后 second（后半）长度 ≤ first（前半），以 second 是否走完为终止条件最稳，前半多出的尾节点天然留在最后。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把重排链表一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →重排链表交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 143中等链表

重排链表图解题解

一条链表，把头尾交替穿插重排——快慢找中点、反转后半、交替合并，全程不借额外空间。

这道题到底在问什么

给定单链表 L0→L1→…→Ln，原地重排为 L0→Ln→L1→Ln-1→L2→Ln-2→…，不改节点值、只改指针。

输入: 1→2→3→4→5→6
输出: 1→6→2→5→3→4
输入: 1→2→3→4→5
输出: 1→5→2→4→3

最优解：一步一步想明白

3记住这三步：找中点 → 反转后半 → 交替合并。下面逐帧看清每一步指针怎么动。
4找中点用快慢指针：slow 一次走 1 格、fast 一次走 2 格，都从头出发。fast 到尽头时，slow 正好停在中点。
5第 1 轮：slow 先稳稳走 1 格到下标 1。接着看 fast 跨两格——拆两小跳看清楚。
6fast 的第一小跳：跨到下标 1。
7fast 的第二小跳：再跨到下标 2。slow 走 1、fast 走 2 的 2 倍速，让 fast 到头时 slow 恰好在中点。
8第 2 轮：slow 先稳稳走 1 格到下标 2。接着看 fast 跨两格——拆两小跳看清楚。
9fast 的第一小跳：跨到下标 3。
10fast 的第二小跳：再跨到下标 4。slow 走 1、fast 走 2 的 2 倍速，让 fast 到头时 slow 恰好在中点。
11fast 走到链表最后一个节点（下标 5），无法再跨两格，找中点结束。此刻 slow 停在下标 3，正是正中间。
12劈分完成：前半是下标 0…2（绿色，共 3 个），后半是下标 3…5（共 3 个）。slow 指向后半的第一个，下一步把后半整段反转。
13先把前半和后半断开：前半最后一个（下标 2）的 next 置空（中间那根连线变 ·）。cur 从后半头下标 3 起步，prev 初始为空。
14掉头前先存好后继：nxt = cur.next = 下标 4。不先存，掉头后就找不到下一个了（链表题最常见的丢 next 坑）。
15掉头前先存好后继：nxt = cur.next = 下标 5。不先存，掉头后就找不到下一个了（链表题最常见的丢 next 坑）。
16把 cur(下标 4) 的箭头掉头指向 prev(下标 3)：那根连线变 ←。后半段被一节一节翻过来。
17cur 在下标 5，它是后半最后一个，nxt 为空。
18把 cur(下标 5) 的箭头掉头指向 prev(下标 4)：那根连线变 ←。后半段被一节一节翻过来。
19后半反转完成：head2 落在下标 5（原来的最后一个 6），它是反转后半的新头。现在前半 1→2→3、反转后半 6→5→4，准备交替合并。
20把链表摆成两行：上「前半 1→2→3」、中「反转后半 6→5→4」，下面是空的结果行。head1 指前半头、head2 指后半头，从前半先取。
21轮到取前半：head1 指向 1（下标 0），把它接到结果尾。
22把 1 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
23轮到取后半：head2 指向 6（下标 0），把它接到结果尾。前后交替是重排的关键。
24把 6 接到结果尾（变绿），后半取走的节点标灰、指针前移。下一节轮到取前半。
25轮到取前半：head1 指向 2（下标 1），把它接到结果尾。
26把 2 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
27轮到取后半：head2 指向 5（下标 1），把它接到结果尾。前后交替是重排的关键。
28把 5 接到结果尾（变绿），后半取走的节点标灰、指针前移。下一节轮到取前半。
29轮到取前半：head1 指向 3（下标 2），把它接到结果尾。
30把 3 接到结果尾（变绿），前半取走的节点标灰、指针前移。下一节轮到取后半。
31轮到取后半：head2 指向 4（下标 2），把它接到结果尾。前后交替是重排的关键。
32把 4 接到结果尾（变绿），后半取走的节点标灰、指针前移。两半都取完，重排结束。
33两半接完，结果 1→6→2→5→3→4。回头核一遍：第 1 位 1 来自前半头。
34第 2 位 6 来自后半（从尾往回），前后交替无误。
35第 3 位 2 来自前半，前后交替无误。
36第 4 位 5 来自后半（从尾往回），前后交替无误。
37第 5 位 3 来自前半，前后交替无误。
38最后一位 4。整条 1→6→2→5→3→4 正是 L0→Ln→L1→Ln-1→… 的头尾交替，重排正确。

⚠️ 容易写错的地方

✗ 错：反转后半时直接改 next

✓ 对：先 nxt = cur.next 存好后继再掉头

不先存，掉头后整条后半就断了，找不到下一个

✗ 错：忘了断开前后两半

✓ 对：slow.next = null 先断开

不断开，合并时会绕回前半形成环，死循环

✗ 错：合并时丢失下一个节点

✓ 对：先把 first.next / second.next 都存到 n1 / n2 再改指针

改了 first.next 就找不到前半的下一个了

完整代码（Python / Java / JavaScript / C++）

Python

def reorderList(head):
    if not head or not head.next: return
    # ① 快慢找中点
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # ② 反转后半（从 slow.next 起）
    second = slow.next
    slow.next = None      # 断开前后两半
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    # ③ 前后交替合并
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

Java

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        // ① 快慢找中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // ② 反转后半（从 slow.next 起）
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode nxt = second.next;
            second.next = prev;
            prev = second;
            second = nxt;
        }
        // ③ 前后交替合并
        ListNode first = head;
        second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1; second = n2;
        }
    }
}

JavaScript

function reorderList(head) {
  if (!head || !head.next) return;
  // ① 快慢找中点
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // ② 反转后半（从 slow.next 起）
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second) {
    const nxt = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  // ③ 前后交替合并
  let first = head;
  second = prev;
  while (second) {
    const n1 = first.next, n2 = second.next;
    first.next = second;
    second.next = n1;
    first = n1; second = n2;
  }
}

C++

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    // ① 快慢找中点
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // ② 反转后半（从 slow->next 起）
    ListNode* second = slow->next;
    slow->next = nullptr;
    ListNode* prev = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev;
        prev = second;
        second = nxt;
    }
    // ③ 前后交替合并
    ListNode* first = head;
    second = prev;
    while (second) {
        ListNode* n1 = first->next;
        ListNode* n2 = second->next;
        first->next = second;
        second->next = n1;
        first = n1; second = n2;
    }
}

复杂度

时间

O(n)

找中点走半条 + 反转半条 + 合并半条，都是线性

空间

O(1)

原地反转后半 + 原地接线，只用常数个指针，不新建节点

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着重排链表的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么用 fast.next && fast.next.next 而不是 fast && fast.next？+

前者让 slow 停在前半最后一个（偶数时偏前），slow.next 才是后半头，劈分更干净；后者会让 slow 偏到后半。

能不能不反转、用栈做？+

可以：把后半压栈，再前半逐个与栈顶交替接。但栈是 O(n) 空间，不满足进阶的 O(1)。

合并循环用 while(second) 还是 while(first)？+

反转后 second（后半）长度 ≤ first（前半），以 second 是否走完为终止条件最稳，前半多出的尾节点天然留在最后。

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →重排链表交互动画,逐步看清每一步怎么走

重排链表 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / Java / JavaScript / C++）

Python

Java

JavaScript

C++

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

重排链表 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / Java / JavaScript / C++）

Python

Java

JavaScript

C++

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

重排链表图解题解

重排链表图解题解