力扣143.重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln – 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln – 1 → L2 → Ln – 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

思路一（数组）

用ArrayList 存储所有链表节点，在用双指针（左右指针）按要求实现链表重排。

具体步骤与解析

1.边界处理（空链表或只有一个节点，无需重排）

if (head == null || head.next == null) return;

2.将所有链表节点存入ArrayList中

ListNode cur = head;
List<ListNode> list = new ArrayList<>();
while (cur != null) {
list.add(cur);
cur = cur.next;
}

使用ArrayList（动态数组）能能快速拿到任意下标对应的节点。

3.双指针交替拼接链表

cur = head; // 回到头节点，作为拼接起点
int l = 1, r = list.size() – 1; // l从1开始（跳过已用的头节点），r指向最后一个节点
int count = 0;

while (l <= r) {
if (count % 2 == 0) {
// 偶数次：取右指针（尾方向）的节点
cur.next = list.get(r);
r–; // 右指针左移
} else {
// 奇数次：取左指针（头方向）的节点
cur.next = list.get(l);
l++; // 左指针右移
}
cur = cur.next; // 拼接后指针后移
count++; // 控制取节点的方向
}

count 用于控制 “取尾 / 取头” 的交替逻辑。

4.切断循环引用

// 关键：切断最后一个节点的后续引用，避免链表成环
cur.next = null;

因为原节点仍保留着原本的next引用（比如节点 3 原本指向 4），若不切断，重排后的最后一个节点会指向原链表的后续节点，导致链表成环。

完整代码

class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode cur = head;
List<ListNode> list = new ArrayList<>();
while (cur != null) {
list.add(cur);
cur = cur.next;
}
cur = head;
int l = 1, r = list.size() – 1;
int count = 0;

while (l <= r) {
if (count % 2 == 0) {
cur.next = list.get(r);
r–;
} else {
cur.next = list.get(l);
l++;
}
cur = cur.next;
count++;
}
cur.next = null;
}
}

思路二

利用双端队列 “头尾都能取元素” 的特性，实现链表 “头→尾→次头→次尾” 的重排效果。

*补充

队列：是一种先进先出的线性数据结构，就像“排队办事”。核心是从队尾添加元素从队首删除并取出元素。

双端队列：是队列的 “升级版”，核心是两端都能入队、两端都能出队。

具体步骤与解析

1.边界处理

if (head == null || head.next == null) {
return;
}

2.初始化双端队列，存入除头节点外的所有节点

Deque<ListNode> de = new LinkedList<>();
ListNode cur = head.next; // 头节点保留，从第二个节点开始入队
while (cur != null) {
de.offer(cur); // 节点加入队列尾部
cur = cur.next;
}

头节点是重排的起点，直接作为第一个节点使用,若入队，会导致重排后开头重复

3.从头部开始，交替拼接队列尾/头节点

cur = head; // 回到头节点，作为拼接起点
int count = 0;
while (!de.isEmpty()) {
if (count % 2 == 0) {
// 偶数次：取队列尾部（原链表的尾节点）
cur.next = de.pollLast();
} else {
// 奇数次：取队列头部（原链表的次头节点）
cur.next = de.poll();
}
cur = cur.next; // 指针后移到新拼接的节点
count++;
}

4.切断循环引用

// 关键：切断最后一个节点的后续引用，避免链表成环
cur.next = null;

完整代码

class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
Deque<ListNode> de = new LinkedList<>();
ListNode cur = head.next;
while (cur != null) {
de.offer(cur);
cur = cur.next;
}
cur = head;
int count = 0;
while (!de.isEmpty()) {
if (count % 2 == 0) {
cur.next = de.pollLast();
} else {
cur.next = de.poll();
}
cur = cur.next;
count++;
}
cur.next = null;
}
}