-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortList.java
46 lines (46 loc) · 1.19 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
/**
* 148. Sort List
* 链表排序
* @author LBW
*/
public class SortList {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// find the mid
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// cut the mid.
ListNode tmp = slow.next;
slow.next = null;
// sort two lists
ListNode left = sortList(head);
ListNode right = sortList(tmp);
// merge
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
cur.next = left;
cur = cur.next;
left = left.next;
}
else {
cur.next = right;
cur = cur.next;
right = right.next;
}
}
if (left != null) {
cur.next = left;
}
else if (right != null) {
cur.next = right;
}
return dummy.next;
}
}