leetcode

commit e549c87028ba7f9fdaa34b547851b79e97a0e8c7
parent 0e9cc7a3a0215e45e727bf560d4149f4cea05ed9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  7 Feb 2023 18:11:05 +0100

LeetCode 75 II: Day 4

Diffstat:
A
Problems/0148.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0148.cpp b/Problems/0148.cpp
@@ -0,0 +1,38 @@
+class Solution {
+public:
+  ListNode *sortList(ListNode *head) {
+    if (!head || !head->next) return head;
+    ListNode *mid = getMid(head), *left = sortList(head),
+             *right = sortList(mid);
+    return merge(left, right);
+  }
+
+  ListNode *merge(ListNode *list1, ListNode *list2) {
+    ListNode head, *t = &head;
+
+    while (list1 && list2) {
+      if (list1->val < list2->val) {
+        t = t->next = list1;
+        list1 = list1->next;
+      } else {
+        t = t->next = list2;
+        list2 = list2->next;
+      }
+    }
+
+    t->next = list1 ? list1 : list2;
+    return head.next;
+  }
+
+  ListNode *getMid(ListNode *head) {
+    ListNode *fast, *slow;
+    fast = slow = head;
+    while (fast->next && fast->next->next) {
+      fast = fast->next->next;
+      slow = slow->next;
+    }
+    fast = slow->next;
+    slow->next = nullptr;
+    return fast;
+  }
+};
diff --git a/README.md b/README.md
@@ -114,6 +114,7 @@ for solving problems.
 |  0143  |   Medium   | [Reorder List](Problems/0143.cpp)                                                                |
 |  0144  |   Medium   | [Binary Tree Preorder Traversal](Problems/0144.cpp)                                              |
 |  0145  |    Easy    | [Binary Tree Postorder Traversal](Problems/0145.cpp)                                             |
+|  0148  |   Medium   | [Sort List](Problems/0148.cpp)                                                                   |
 |  0149  |    Hard    | [Max Points on a Line](Problems/0149.cpp)                                                        |
 |  0150  |   Medium   | [Evaluate Reverse Polish Notation](Problems/0150.cpp)                                            |
 |  0151  |   Medium   | [Reverse Words in a String](Problems/0151.cpp)                                                   |