-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_148.java
More file actions
39 lines (35 loc) · 1.07 KB
/
Copy pathP_148.java
File metadata and controls
39 lines (35 loc) · 1.07 KB
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
package leetcode.medium;
import utils.DataStructures.ListNode;
@SuppressWarnings("ConstantConditions")
public class P_148 {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
final ListNode temp = slow.next;
slow.next = null;
return merge(sortList(head), sortList(temp));
}
private static ListNode merge(ListNode up, ListNode down) {
final ListNode merge = new ListNode(-1);
ListNode iter = merge;
while (up != null && down != null) {
if (up.val < down.val) {
iter.next = up;
up = up.next;
} else {
iter.next = down;
down = down.next;
}
iter = iter.next;
}
iter.next = up != null ? up : down;
return merge.next;
}
}