-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortList.java
97 lines (74 loc) · 2.84 KB
/
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
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
// Technique: Merge sort
/**
* O(nlogn) time & O(1) space
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode midNode = splitToHalf(head);
ListNode leftHalf = sortList(head);
ListNode rightHalf = sortList(midNode);
return merge(leftHalf, rightHalf);
}
private ListNode splitToHalf(ListNode startNode) {
ListNode prevNode = null;
ListNode slowPointer = startNode;
ListNode fastPointer = startNode;
// Fast pointer will run twice as fast as the slow one.
// Hence when it reaches the last node, slow pointer will
// be at mid node
while (fastPointer != null && fastPointer.next != null) {
prevNode = slowPointer;
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
}
prevNode.next = null; // cut off list in half, will be last node of left half
return slowPointer; // will be the first node of right half
}
private ListNode merge(ListNode leftHalfPointer, ListNode rightHalfPointer) {
ListNode dummyHead = new ListNode(0);
ListNode endOfSortedList = dummyHead;
while (leftHalfPointer != null && rightHalfPointer != null) {
// whichever one is smaller, will be appended to the list
if (leftHalfPointer.val < rightHalfPointer.val) {
endOfSortedList.next = leftHalfPointer;
leftHalfPointer = leftHalfPointer.next;
} else {
endOfSortedList.next = rightHalfPointer;
rightHalfPointer = rightHalfPointer.next;
}
endOfSortedList = endOfSortedList.next; // move pointer forward
}
// if right half reaches end of its list first, while left still have
// 1 node left, just append it
if (leftHalfPointer != null)
endOfSortedList.next = leftHalfPointer;
if (rightHalfPointer != null)
endOfSortedList.next = rightHalfPointer;
return dummyHead.next;
}
}
/**
* O(nlogn) time & O(n) space with n = number of nodes
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
List<Integer> nodeValues = new ArrayList<>();
while (head != null) {
nodeValues.add(head.val);
head = head.next;
}
Collections.sort(nodeValues);
ListNode resultPointer = new ListNode(0);
ListNode newHead = new ListNode(nodeValues.get(0));
resultPointer.next = newHead;
for (int i = 1; i < nodeValues.size(); i++) {
newHead.next = new ListNode(nodeValues.get(i));
newHead = newHead.next;
}
return resultPointer.next;
}
}