-
Notifications
You must be signed in to change notification settings - Fork 0
/
0148-sort-list.java
55 lines (45 loc) · 1.41 KB
/
0148-sort-list.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
public class Solution {
//merge two sorted list, return result head
public ListNode merge(ListNode h1, ListNode h2){
if(h1 == null){
return h2;
}
if(h2 == null){
return h1;
}
if(h1.val < h2.val){
h1.next = merge(h1.next, h2);
return h1;
}
else{
h2.next = merge(h1, h2.next);
return h2;
}
}
public ListNode sortList(ListNode head) {
//bottom case
if(head == null){
return head;
}
if(head.next == null){
return head;
}
//p1 move 1 step every time, p2 move 2 step every time, pre record node before p1
ListNode p1 = head;
ListNode p2 = head;
ListNode pre = head;
// 2칸씩 전진하는 포인터와 1칸씩 전진하는 포인터로 나눠 절반 지점을 찾는 건 천재적인 것 같다.
while(p2 != null && p2.next != null){
pre = p1;
p1 = p1.next;
p2 = p2.next.next;
}
//change pre next to null, make two sub list(head to pre, p1 to p2)
pre.next = null;
// 절단 지점에서 끊기
//handle those two sub list
ListNode h1 = sortList(head);
ListNode h2 = sortList(p1);
return merge(h1, h2);
}
}