https://leetcode.com/problems/sort-list/
Merge Sort ( recurrence and divide-and-conquer)\
Time Complexity: O(NlogN), Space Complexity: O(logN)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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null) return head;
ListNode pre=null,slow=head,fast=head;
while(fast!=null&&fast.next!=null){
pre=slow;
slow=slow.next;
fast=fast.next.next;
}
pre.next=null;
ListNode l1=sortList(head);
ListNode l2=sortList(slow);
return mergeList(l1,l2);
}
public ListNode mergeList(ListNode l1,ListNode l2){
ListNode l=new ListNode(0),p=l;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
p.next=l1;
l1=l1.next;
}else{
p.next=l2;
l2=l2.next;
}
p=p.next;
}
if(l1==null) p.next=l2;
if(l2==null) p.next=l1;
return l.next;
}
}
Merge Sort ( divide-and-conquer by Bottom-Up)\
Time Complexity: O(NlogN), Space Complexity: 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
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int n = 0;
while (head != null) {
head = head.next;
n++;
}
for (int step = 1; step < n; step <<= 1) {
ListNode prev = dummy;
ListNode cur = dummy.next;
while (cur != null) {
ListNode left = cur;
ListNode right = split(left, step);
cur = split(right, step);
prev = merge(left, right, prev);
}
}
return dummy.next;
}
/**
* Divide the linked list into two lists,
* while the first list contains first n ndoes
* return the second list's head
*/
private ListNode split(ListNode head, int step) {
if (head == null) return null;
for (int i = 1; head.next != null && i < step; i++) {
head = head.next;
}
ListNode right = head.next;
head.next = null;
return right;
}
/**
* merge the two sorted linked list l1 and l2,
* then append the merged sorted linked list to the node head
* return the tail of the merged sorted linked list
*/
private ListNode merge(ListNode left, ListNode right, ListNode prev) {
ListNode cur = prev;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
if (left != null)cur.next = left;
else if (right != null)cur.next = right;
while (cur.next != null) cur = cur.next;
return cur;
}
}
public class lc148 {
public static void main(String[] args) {
// 4->1->3->2
ListNode head = new ListNode(4);
head.next = new ListNode(1);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(2);
//before sorting
System.out.println("before sorting:");
ListNode dummy=head;
while (dummy.next != null) {
System.out.print(dummy.val+"->");
dummy = dummy.next;
}
System.out.println(dummy.val);
//after sorting
System.out.println("after sorting:");
ListNode res = new Solution().sortList(head);
while (res.next != null) {
System.out.print(res.val+"->");
res = res.next;
}
System.out.println(res.val);
}
}