add 49, update 148

rustykitty · rustykitty · commit 664da4e502a8 · 2025-02-14T00:37:00.000Z
diff --git a/0049-group-anagrams.py b/0049-group-anagrams.py
@@ -0,0 +1,13 @@
+"""
+49. Group Anagrams
+
+Submitted: February 11, 2025
+
+Runtime: 21 ms (beats 24.46%)
+Memory: 20.82 MB (beats 56.56%)
+"""
+
+class Solution:
+    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
+        strs.sort(key=sorted)
+        return [list(group) for (key, group) in itertools.groupby(strs, key=sorted)]
diff --git a/0148-sort-list.cpp b/0148-sort-list.cpp
@@ -1,10 +1,10 @@
 /*
 148. Sort List
 
-Submitted: February 10, 2025
+Submitted: February 11, 2025
 
-Runtime: 7 ms (beats 96.37%)
-Memory: 58.09 MB (beats 75.27%)
+Runtime: 7 ms (beats 96.40%)
+Memory: 55.79 MB (beats 99.18%)
 */
 
 /**
@@ -17,14 +17,43 @@ Memory: 58.09 MB (beats 75.27%)
  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  * };
  */
-class Solution {
-public:
-    ListNode* sortList(ListNode* head) {
-        vector<int> v;
-        for (ListNode* p = head; p != nullptr; p = p->next) v.push_back(p->val); 
-        sort(v.begin(), v.end());
-        auto it = v.cbegin();
-        for (ListNode* p = head; p != nullptr && it != v.cend(); p = p->next, ++it) p->val = *it;
-        return head;
-    }
-};
+
+ class Solution {
+    public:
+        ListNode* sortList(ListNode* head) {
+            if (head == nullptr || head->next == nullptr) return head;
+            int size = 0;
+            for (ListNode* p = head; p != nullptr; p = p->next) ++size;
+            if (size == 2) {
+                if (head->val > head->next->val) swap(head->val, head->next->val);
+                return head;
+            }
+            ListNode* beforeHalf = head;
+            for (int i = 0; i < (size / 2) - 1; ++i) beforeHalf = beforeHalf->next;
+            ListNode* half = beforeHalf->next;
+            beforeHalf->next = nullptr;
+            ListNode* newHead = mergeTwoLists(sortList(head), sortList(half));
+            return newHead;
+        }
+        // from 21-merge-two-sorted-lists
+        ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
+            if (list1 == nullptr) return list2;
+            if (list2 == nullptr) return list1;
+            ListNode* head = list1->val > list2->val ? list2 : list1;
+            if (head == list1) list1 = list1->next;
+            else list2 = list2->next;
+            ListNode* tail = head;
+            while (list1 != nullptr && list2 != nullptr) {
+                if (list1->val > list2->val) {
+                    tail->next = list2;
+                    list2 = list2->next;
+                } else {
+                    tail->next = list1;
+                    list1 = list1->next;
+                }
+                tail = tail->next;
+            }
+            tail->next = list1 == nullptr ? list2 : list1;
+            return head;
+        }
+    };
