问题描述
LeetCode 143. 重排链表 (opens in a new tab)，难度中等。
给定一个单链表 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
题解
Solution.java
class Solution {
public void reorderList(ListNode head) {
// 遍历放入双向队列中
ListNode temp = head;
Deque<ListNode> array = new ArrayDeque<>();
while (temp != null) {
array.add(temp);
temp = temp.next;
}
ListNode curr = head;
array.pollFirst();
int index = 2;
while (!array.isEmpty()) {
if (index % 2 == 1) {
// 取首节点
ListNode first = array.pollFirst();
curr.next = first;
} else {
// 取尾节点
ListNode last = array.pollLast();
curr.next = last;
}
index++;
curr = curr.next;
}
curr.next = null;
}
}