148 Sort List

148. Sort List

1. Question

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

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode sortList(ListNode head) {
11
if (head == null || head.next == null) {
12
return head;
13
}
14
15
int len = 0;
16
ListNode curNode = head;
17
18
while (curNode != null) {
19
curNode = curNode.next;
20
++len;
21
}
22
23
ListNode left = null, right = null, tail = null, dummy = null;
24
for (int step = 1; step < len; step *= 2) {
25
dummy = new ListNode(0);
26
curNode = head;
27
tail = dummy;
28
29
while (curNode != null) {
30
left = curNode;
31
right = split(left, step);
32
curNode = split(right, step);
33
tail = merge(left, right, tail);
34
}
35
head = dummy.next;
36
}
37
return head;
38
}
39
40
// Split a linked list into half, where the first half contains n nodes (or all nodes)
41
// Return the head of the second half list (or null)
42
public ListNode split(ListNode head, int n) {
43
for (int i = 1; head != null && i < n; i++) {
44
head = head.next;
45
}
46
47
if (head == null) {
48
return null;
49
}
50
ListNode second = head.next;
51
head.next = null;
52
return second;
53
}
54
55
// Merge two sorted linked list l1 and l2
56
// Append the result to list node tail
57
// Return the tail of merge sorted list
58
public ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
59
ListNode curNode = tail;
60
while (l1 != null && l2 != null) {
61
if (l1.val < l2.val) {
62
curNode.next = l1;
63
l1 = l1.next;
64
}
65
else {
66
curNode.next = l2;
67
l2 = l2.next;
68
}
69
curNode = curNode.next;
70
}
71
72
curNode.next = l1 == null ? l2 : l1;
73
while (curNode.next != null) {
74
curNode = curNode.next;
75
}
76
return curNode;
77
}
78
}
Copied!

3. Time & Space Complexity

时间复杂度O(nlogn), 空间复杂度O(1)