|
9 | 9 | */
|
10 | 10 | public class _148 {
|
11 | 11 |
|
12 |
| - /**Credit: https://discuss.leetcode.com/topic/18100/java-merge-sort-solution |
13 |
| - * But this is not using constant space.*/ |
14 |
| - public ListNode sortList(ListNode head) { |
15 |
| - if (head == null || head.next == null) { |
16 |
| - return head; |
17 |
| - } |
| 12 | + public static class Solution1 { |
| 13 | + /** |
| 14 | + * Credit: https://discuss.leetcode.com/topic/18100/java-merge-sort-solution |
| 15 | + * But this is not using constant space. |
| 16 | + */ |
| 17 | + public ListNode sortList(ListNode head) { |
| 18 | + if (head == null || head.next == null) { |
| 19 | + return head; |
| 20 | + } |
18 | 21 |
|
19 |
| - //Step 1: split the list into halves |
20 |
| - ListNode prev = null; |
21 |
| - ListNode slow = head; |
22 |
| - ListNode fast = head; |
23 |
| - while (fast != null && fast.next != null) { |
24 |
| - prev = slow; |
25 |
| - fast = fast.next.next; |
26 |
| - slow = slow.next; |
27 |
| - } |
28 |
| - prev.next = null; |
| 22 | + //Step 1: split the list into halves |
| 23 | + ListNode prev = null; |
| 24 | + ListNode slow = head; |
| 25 | + ListNode fast = head; |
| 26 | + while (fast != null && fast.next != null) { |
| 27 | + prev = slow; |
| 28 | + fast = fast.next.next; |
| 29 | + slow = slow.next; |
| 30 | + } |
| 31 | + prev.next = null; |
29 | 32 |
|
30 |
| - //step 2: sort each half |
31 |
| - ListNode l1 = sortList(head); |
32 |
| - ListNode l2 = sortList(slow); |
| 33 | + //step 2: sort each half |
| 34 | + ListNode l1 = sortList(head); |
| 35 | + ListNode l2 = sortList(slow); |
33 | 36 |
|
34 |
| - //step 3: merge the two halves |
35 |
| - return merge(l1, l2); |
36 |
| - } |
| 37 | + //step 3: merge the two halves |
| 38 | + return merge(l1, l2); |
| 39 | + } |
37 | 40 |
|
38 |
| - private ListNode merge(ListNode l1, ListNode l2) { |
39 |
| - ListNode result = new ListNode(0); |
40 |
| - ListNode tmp = result; |
| 41 | + private ListNode merge(ListNode l1, ListNode l2) { |
| 42 | + ListNode result = new ListNode(0); |
| 43 | + ListNode tmp = result; |
41 | 44 |
|
42 |
| - while (l1 != null && l2 != null) { |
43 |
| - if (l1.val < l2.val) { |
| 45 | + while (l1 != null && l2 != null) { |
| 46 | + if (l1.val < l2.val) { |
| 47 | + tmp.next = l1; |
| 48 | + l1 = l1.next; |
| 49 | + } else { |
| 50 | + tmp.next = l2; |
| 51 | + l2 = l2.next; |
| 52 | + } |
| 53 | + tmp = tmp.next; |
| 54 | + } |
| 55 | + |
| 56 | + if (l1 != null) { |
44 | 57 | tmp.next = l1;
|
45 |
| - l1 = l1.next; |
46 |
| - } else { |
| 58 | + } |
| 59 | + if (l2 != null) { |
47 | 60 | tmp.next = l2;
|
48 |
| - l2 = l2.next; |
49 | 61 | }
|
50 |
| - tmp = tmp.next; |
51 |
| - } |
52 |
| - |
53 |
| - if (l1 != null) { |
54 |
| - tmp.next = l1; |
55 |
| - } |
56 |
| - if (l2 != null) { |
57 |
| - tmp.next = l2; |
| 62 | + return result.next; |
58 | 63 | }
|
59 |
| - return result.next; |
60 | 64 | }
|
61 |
| - |
62 | 65 | }
|
0 commit comments