来自Leetcode第143题重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
1
| 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
|
示例 2:
1
| 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
|
空间换时间
创建线性表，依次存储各个链表结点，然后用双指针依次取头尾元素，避免了每次从头遍历.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null)
return;
List<ListNode> list = new ArrayList<>();
while(head != null){
list.add(head);
head = head.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;
}
|
递归
参考 这里。
解法一中也说到了，我们的问题就是取尾元素的时候，需要遍历一遍链表。
如果我们的递归函数能够返回当前头元素对应的尾元素，并且将头元素和尾元素之间的链表按要求完成，那就变得简单了。
如上图，我们只需要将 head 指向 tail，tail 指向处理完的链表头即可。
然后我们把之前的 tail.next 返回就是外层 head 对应的 tail 了。
递归出口的话，如果只有一个节点，那么我们只需要将 head.next 返回。
递归出口的话，如果只有一个节点，那么我们只需要将 head.next 返回。
如果是两个节点，我们需要将 head.next.next 返回。
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
| public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null)
return;
int len = 0;
ListNode ahead = head;
while (ahead != null) {
len++;
ahead = ahead.next;
}
reorderListHelper(head, len);
}
private ListNode reorderListHelper(ListNode head, int len) {
if (len == 1) {
ListNode outTail = head.next;
head.next = null;
return outTail;
}
if (len == 2) {
ListNode outTail = head.next.next;
head.next.next = null;
return outTail;
}
ListNode tail = reorderListHelper(head.next, len - 2);
ListNode subHead = head.next;
head.next = tail;
ListNode outTail = tail.next;
tail.next = subHead;
return outTail;
}
|
分治
参考 这里，主要是利用到一头一尾取元素的特性。
主要是三步，举个例子。
1
2
3
4
5
6
7
8
9
10
11
| 1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步，将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6
第二步，将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4
第三步，依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4
|
第一步找中点的话，可以应用 19 题的方法，快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。
第二步链表逆序的话，在 第 2 题]讨论过了，有迭代和递归的两种方式，迭代的话主要利用两个指针，依次逆转。
第三步的话就很简单了，两个指针分别向后移动就可以。
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
| public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode newHead = slow.next;
slow.next = null;
newHead = reverseList(newHead);
while (newHead != null) {
ListNode temp = newHead.next;
newHead.next = head.next;
head.next = newHead;
head = newHead.next;
newHead = temp;
}
}
private ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode tail = head;
head = head.next;
tail.next = null;
while (head != null) {
ListNode temp = head.next;
head.next = tail;
tail = head;
head = temp;
}
return tail;
}
|