1，问题描述
143. 重排链表
难度：中等
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
1
| L0 → L1 → … → Ln - 1 → Ln
|
请将其重新排列后变为：
1
| L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
|
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
1
2
| 输入：head = [1,2,3,4]
输出：[1,4,2,3]
|
示例 2：
1
2
| 输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
|
提示：
- 链表的长度范围为
[1, 5 * 10^4]
1 <= node.val <= 1000
2，初步思考
有2种求解方法：
1️⃣使用缓存空间，存储索引，然后依次处理
2️⃣直接将链表切分2支，第二支反转，两支在合并
3，代码处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| package questions;
import support.ListNode;
import java.util.HashMap;
import java.util.Map;
public class _143重排链表 {
public void reorderList_cache(ListNode head) {
Map<Integer, ListNode> map = new HashMap<>();
int cnt = 0;
while (head != null) {
map.put(cnt, head);
head = head.next;
cnt++;
}
int n = cnt / 2;
ListNode headTemp, headNextTemp = null, nextTemp = null;
for (int i = 0; i < n; i++) {
headTemp = map.get(i);
headNextTemp = map.get(i + 1);
nextTemp = map.get(cnt - i - 1);
headTemp.next = nextTemp;
nextTemp.next = headNextTemp;
}
if (cnt > 3) {
if (nextTemp != null) nextTemp.next.next = null;
} else {
if (headNextTemp != null) headNextTemp.next = null;
}
}
public void reorderList(ListNode head) {
ListNode newHead = new ListNode();
newHead.next = head;
int cnt = 0;
ListNode slow = head;
ListNode quick = head;
while (quick.next != null) {
cnt++;
quick = quick.next;
if (cnt % 2 == 0) {
slow = slow.next;
}
}
ListNode right = slow.next;
slow.next = null;
right = reverse(right);
head = newHead.next;
while (right != null && head != null) {
ListNode headTemp = head.next;
ListNode rightTemp = right.next;
head.next = right;
right.next = headTemp;
head = headTemp;
right = rightTemp;
}
head = newHead.next;
}
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String[] args) {
_143重排链表 lcr024 = new _143重排链表();
ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
lcr024.reorderList_cache(listNode);
System.out.println();
}
}
|