8000 refactor 148 · adkushal/Leetcode@132a4e1 · GitHub
[go: up one dir, main page]

Skip to content

Commit 132a4e1

Browse files
refactor 148
1 parent 9969294 commit 132a4e1

File tree

1 file changed

+43
-40
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+43
-40
lines changed

src/main/java/com/fishercoder/solutions/_148.java

Lines changed: 43 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -9,54 +9,57 @@
99
*/
1010
public class _148 {
1111

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+
}
1821

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;
2932

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);
3336

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+
}
3740

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;
4144

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) {
4457
tmp.next = l1;
45-
l1 = l1.next;
46-
} else {
58+
}
59+
if (l2 != null) {
4760
tmp.next = l2;
48-
l2 = l2.next;
4961
}
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;
5863
}
59-
return result.next;
6064
}
61-
6265
}

0 commit comments

Comments
 (0)
0