added a O(1) memory solution for 148 sort list (fishercoder1534#163)

Ildar10 · nazmeevi · web-flow · commit b45ab1d08f28 · 2021-10-01T15:08:08.000-07:00
Co-authored-by: nazmeevi &lt;ildar.nazmeev@tipico.com&gt;
diff --git a/README.md b/README.md
@@ -1082,6 +1082,7 @@ _If you like this project, please leave me a star._ &#9733;
 |151|[Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_151.java)| | Medium| String
 |150|[Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_150.java)| |Medium
 |149|[Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_149.java)| |Hard|
+|148|[Sort List](https://leetcode.com/problems/sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_148.java) ||Medium| Linked List, Sorting
 |147|[Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_147.java) ||Medium| Linked List
 |146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_146.java)|  |Hard| Doubly Linked List, LinkedHashMap
 |145|[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_145.java)|[:tv:](https://youtu.be/B6XTLPpsW7k) |Easy| Binary Tree
diff --git a/src/main/java/com/fishercoder/solutions/_148.java b/src/main/java/com/fishercoder/solutions/_148.java
@@ -57,4 +57,86 @@ private ListNode merge(ListNode l1, ListNode l2) {
             return result.next;
         }
     }
+
+    public static class Solution2 {
+        ListNode tail = new ListNode(0);
+        ListNode nextSubList = new ListNode(0);
+
+        public ListNode sortList(ListNode head) {
+            if (head == null || head.next == null)
+                return head;
+            int n = getCount(head);
+            ListNode start = head;
+            ListNode dummyHead = new ListNode(0);
+            for (int size = 1; size < n; size = size * 2) {
+                tail = dummyHead;
+                while (start != null) {
+                    if (start.next == null) {
+                        tail.next = start;
+                        break;
+                    }
+                    ListNode mid = split(start, size);
+                    merge(start, mid);
+                    start = nextSubList;
+                }
+                start = dummyHead.next;
+            }
+            return dummyHead.next;
+        }
+
+        ListNode split(ListNode start, int size) {
+            ListNode midPrev = start;
+            ListNode end = start.next;
+            //use fast and slow approach to find middle and end of second linked list
+            for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
+                if (end.next != null) {
+                    end = (end.next.next != null) ? end.next.next : end.next;
+                }
+                if (midPrev.next != null) {
+                    midPrev = midPrev.next;
+                }
+            }
+            ListNode mid = midPrev.next;
+            midPrev.next = null;
+            nextSubList = end.next;
+            end.next = null;
+            // return the start of second linked list
+            return mid;
+        }
+
+        void merge(ListNode list1, ListNode list2) {
+            ListNode dummyHead = new ListNode(0);
+            ListNode newTail = dummyHead;
+            while (list1 != null && list2 != null) {
+                if (list1.val < list2.val) {
+                    newTail.next = list1;
+                    list1 = list1.next;
+                    newTail = newTail.next;
+                } else {
+                    newTail.next = list2;
+                    list2 = list2.next;
+                    newTail = newTail.next;
+                }
+            }
+            newTail.next = (list1 != null) ? list1 : list2;
+            // traverse till the end of merged list to get the newTail
+            while (newTail.next != null) {
+                newTail = newTail.next;
+            }
+            // link the old tail with the head of merged list
+            tail.next = dummyHead.next;
+            // update the old tail to the new tail of merged list
+            tail = newTail;
+        }
+
+        int getCount(ListNode head) {
+            int cnt = 0;
+            ListNode ptr = head;
+            while (ptr != null) {
+                ptr = ptr.next;
+                cnt++;
+            }
+            return cnt;
+        }
+    }
 }
