今天带着大家解决一道重排链表的问题，是Leetcode第143号问题，题目链接如下：
https://leetcode.com/problems/reorder-list/
想象一个双向队列，从头从尾交替出列（关键点在于找到最后的节点，或者说如何逆序进入链表）
- 递归法
- 入栈法
- 逆转链表法
首先是递归的方法
递归的逻辑
我们首先要找到最后一个节点提到最前，之后我们每逢遇到单数节点，就将之后的节点进行更改。
递归的终点
当只有一个或者两个节点的时候就不必再调整顺序了
具体的代码展示：
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
public void reorderList(ListNode head) {
// 如果为空或者只有一个节点直接返回
// 也可以判断两个节点的情况，但之后也会考虑到
if(head == null || head.next == null){
return;
}
ListNode node = head;
// node的位置是 1、2、3，null
// 所以要判断是否为null，为空则到了结尾
// 若next为空则只剩一个节点，不需再排序
while(node != null && node.next != null){
node.next = update(node.next);
node = node.next.next;
}
}
public ListNode update(ListNode head){
// 承接上一步的更新，node为1、2、3，
// 如果是空，或者只有一个节点就直接返回
if(head == null || head.next == null)return head;
ListNode node = head;
// 找到最后一个几点的前一个
while(node.next.next != null){
node = node.next;
}
// 最后一个绩点为newHead
ListNode newHead = node.next;
// 前一个节点进行断开，不然就成了循环链表
node.next = null;
// 将最后一个节点作为 newHead 放在最前面
newHead.next = head;
return newHead;
}
入栈的方法
我们知道如何将一堆元素的顺序反过来，最容易想到的就是栈，后进先出（LIFO）的特点，是一个天然的逆转链表的方式。
那么我们需要做的就是将链表的后半部分，按照一个个的节点依次入栈
重新连接的时候再逆序出栈就可以了。
找中点的方法我们可以用双指针，一个两倍速，一个单倍速，就可以通过差值找到中点的位置了。
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
public void reorderList(ListNode head) {
// 使用双指针找到中点的位置，并进行标记
ListNode slow = head;
ListNode fast = head;
if(head.next==null)
return ;
while(fast!=null && fast.next!=null){
slow= slow.next;
fast = fast.next.next;
}
fast = slow;
// 开始入栈
Stack<ListNode> stack =new Stack<>();
while(slow!=null){
// 使用临时节点记录位置，并将连接断开依次入栈
ListNode temp = slow;
slow = slow.next;
temp.next = null;
stack.push(temp);
}
// 返回开始点，依次连接正序链表和出栈的节点
// 直到到标记的中点结束
slow = head;
while(slow!=fast ){
ListNode temp = slow.next;
slow.next = stack.pop();
slow = slow.next;
if(slow!= temp){
slow.next = temp;
slow = slow.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
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
// 直接排序
// 找中点
public static ListNode mid(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 中点之后的节点进行逆序，这样就相当于栈了
public static ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode prev = null;
ListNode curr = head;
ListNode frwd = null;
while(curr != null){
frwd = curr.next;
curr.next = prev;
prev = curr;
curr = frwd;
}
return prev;
}
// 重新按需连接
public void reorderList1(ListNode head) {
if(head == null || head.next == null){
return;
}
// 找到中点和中点的下一位方便逆转
ListNode mid_ = mid(head);
ListNode nhead = mid_.next;
mid_.next = null;
nhead = reverse(nhead);
// 两段的开头，分别代表着链表正序和逆序，各一半的链
ListNode c1 = head;
ListNode c2 = nhead;
ListNode f1 = null;
ListNode f2 = null;
// 头节点+尾节点+下一组
while(c2 != null){
f1 = c1.next;
f2 = c2.next;
// 头节点连尾节点
c1.next = c2;
// 连接下一组
c2.next = f1;
c1 = f1;
c2 = f2;
}
}
这样就完成了重拍链表的需求了！关注我，学习更多算法知识。
