-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
147.java
84 lines (79 loc) · 2.51 KB
/
147.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
__________________________________________________________________________________________________
sample 1 ms submission
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode merge(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = merge(l1.next,l2);
return l1;
}else
l2.next = merge(l1,l2.next);
return l2;
}
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null ) return head;
ListNode slow = head,fast = head;
/* find the middle of the list */
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;
slow.next = null;
slow = head;
slow = insertionSortList(slow);
fast = insertionSortList(fast);
return merge(slow,fast);
}
}
__________________________________________________________________________________________________
sample 34596 kb submission
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode headPointer = newHead;
while (headPointer.next != null) {
ListNode min = null;
ListNode prev = null;
ListNode pointer = headPointer;
while (pointer.next != null) {
if (min == null) {
min = pointer.next;
prev = pointer;
} else {
if (pointer.next.val < min.val) {
min = pointer.next;
prev = pointer;
}
}
pointer = pointer.next;
}
if (min != null) {
prev.next = prev.next.next;
min.next = headPointer.next;
headPointer.next = min;
}
headPointer = headPointer.next;
}
return newHead.next;
}
}
__________________________________________________________________________________________________