我要啦免费统计

Sort Linked List Using Contant Space

Sort a linked list in O(n log n) time using constant space complexity.

The requirement on the time complexity of O(n log n) inspires us to use merge sort on linked list. However, the tricky part of this problem is to only use constant space. The normal top down merge sort does not satisfy this requirement, since it requires additional space.

The solution is to use bootom up merge sort.

sortList.java
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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
ListNode move(ListNode head, int moveBy) {
while(head!=null && moveBy-- > 0)
head=head.next;
return head;
}
ListNode merge(ListNode loop, int length) {
if (loop==null || loop.next==null)
//this will help break the for loop in the sortList
return null;
ListNode start1 = loop.next;
ListNode end1 = move(start1, length/2-1);
if (end1 == null)
return null;
ListNode start2 = end1.next;
end1.next = null;
ListNode end2 = move(start2, length/2-1);
ListNode end2next = (end2!=null)? end2.next: null;
if (end2next!=null)
end2.next = null;
while (start1!=null || start2!=null) {
if (start2==null || (start1!=null && start1.val < start2.val)) {
loop.next = start1;
start1=start1.next;
loop=loop.next;
} else {
loop.next = start2;
start2=start2.next;
loop=loop.next;
}
}
loop.next=end2next;
return loop;
}
ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
for (int k=2; true; k*=2) {
int nMerges = 0;
ListNode loop = dummy;
while(loop!=null && loop.next!=null) {
loop = merge(loop, k);
nMerges++;
}
//only one sorted run?
if (nMerges<=1)
break;
}
return dummy.next;
}
}