#143
中等
高频
迭代法重排链表
这是一道围绕链表展开的高频练习。建议先掌握「迭代法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
链表
题目分析
给你一条链表，要求把它重新排成：
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...
不能只改节点值，而要真正调整节点之间的连接关系。
一句话概括：
把链表前半段和后半段倒序后交替拼接起来。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：先找中点，再反转后半段，最后把前半段和反转后的后半段交替合并。
推荐代码
推荐解法：迭代法
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 先找中点，再反转后半段，最后把前半段和反转后的后半段交替合并。
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会拆成三步：找中点、反转后半段、交替合并。
核心过程
- 先用快慢指针找到中点并切开链表。
- 把后半段原地反转，让尾节点顺序变成从前往后可访问。
- 再把前半段和反转后的后半段交替拼接。
- 这样就能得到题目要求的重排顺序。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题真正要背的是三段式模板，不是整段代码。
核心思路
重排链表是三段模板题：找中点、翻后半、交替合并。每一段单独都不复杂，难点在于理解为什么要先把后半段反过来。
步骤讲解
1
快慢指针找链表中点
先找到链表中间位置，并把链表切成前后两段。
为什么这样做：后续要把尾部节点交替插回前半段，必须先拿到后半段入口。
对应代码提示：while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
2
反转后半段链表
把后半段原地反转，使原来的尾节点变成新头节点。
为什么这样做：题目要求交替取首尾节点，反转后半段后就能从前往后顺序合并。
对应代码提示：ListNode second = reverse(slow.next);
3
两段链表交替合并
让第一段和反转后的第二段依次穿插连接，形成 L0 -> Ln -> L1 -> Ln-1 ...。
为什么这样做：反转后，后半段节点顺序已经满足题目需要的尾部访问顺序。
对应代码提示：first.next = second; second.next = firstNext;
易错点
没把前后两段断开
合并时容易形成环或重复连接。
正确理解：找到中点后先把前半段尾部断开。
直接从尾部找节点交替拼接
这样每次都要线性扫描，复杂度会退化成平方级。
正确理解：先反转后半段，再线性交替合并。
交替合并时没先保存 next
链表重连顺序错了就会丢节点。
正确理解：每轮合并前先保存两边的后继节点。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比借数组保存节点再重排更省空间，也更符合链表原地操作要求。
适用判断：链表题出现“首尾交替重排”时，优先想到中点 + 反转 + 合并。
额外提醒
- 先反转后半段，是把“从尾部取节点”转成线性操作的关键。
动画演示
如果你还没完全看懂，可以展开动画演示。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入链表值（用逗号分隔），然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。