解题思路：
在O(NlogN)时间复杂度和O(1)常数空间复杂度对链表进行排序。
代码：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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119快排思路：
Java:
public ListNode sortList(ListNode head) {
QuickSort(head,null);
return head;
}
private void QuickSort(ListNode head,ListNode tail){
if(head == tail || head.next == tail) return;
int pivot = head.val;//使得左边的值都小于pivot，右边的值都不小于pivot
ListNode left = head,cur = head.next;
while(cur != tail){
if(cur.val < pivot){
left = left.next;
//swap(left.val,cur.val);
int t = left.val;
left.val = cur.val;
cur.val = t;
}
cur = cur.next;
}
//swap(head.val,left.val);
int t = head.val;
head.val = left.val;
left.val = t;
QuickSort(head,left);
QuickSort(left.next,tail);
}
//https://leetcode-cn.com/problems/sort-list/solution/gui-bing-pai-xu-he-kuai-su-pai-xu-by-a380922457/
归并思路：
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
int len = getLength(head);
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode pre,cur;
for(int m = 1;m<len;m *= 2){//每次片段长度为 1 2 4 8...
//从开头开始
pre = newHead;
cur = pre.next;
//每次选择两部分，归并排序成一部分,因为每次长度
while(cur != null){
//first是第一部分
ListNode first = cur;
for(int i = 0;i< m-1 && cur != null; i++){
cur = cur.next;
}
if(cur == null) break;//如果第一部分长度不满足，就跳出这次选择
//第一部分和第二部分断开
ListNode second = cur.next;
cur.next = null;
//second是第二部分
cur = second;
for(int i= 0;i< m-1 && cur != null;i++){
cur = cur.next;
}
//剩下部分和第二部分断开
ListNode remain = null;
if(cur != null){ //如果第二部分后面还有
remain = cur.next;
cur.next = null;
}
cur = remain;//为下一次两部分的操作做准备
ListNode tmp = merge(first,second);
pre.next = tmp;
while(pre.next != null){//pre遍历到此次归并链表的结尾
pre = pre.next;
}
pre.next = remain;//接上剩下未排序的元素
}
}
return newHead.next;
}
//获取链表长度
private int getLength(ListNode head){
int length = 0;
ListNode cur = head;
while(cur != null){
length ++;
cur = cur.next;
}
return length;
}
//合并两个有序链表
private ListNode merge(ListNode l1,ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode newHead = new ListNode(0);
ListNode cur = newHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null) cur.next = l1;
if(l2 != null) cur.next = l2;
return newHead.next;
}
//https://leetcode-cn.com/problems/sort-list/solution/20200331148mediandie-dai-fa-gui-bing-pai-xu-bottom/
