leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0148.cpp (991B)

      1 class Solution {
      2   public:
      3     ListNode *sortList(ListNode *head) {
      4         if (!head || !head->next) return head;
      5         ListNode *mid = getMid(head), *left = sortList(head), *right = sortList(mid);
      6         return merge(left, right);
      7     }
      8 
      9     ListNode *merge(ListNode *list1, ListNode *list2) {
     10         ListNode head, *t = &head;
     11 
     12         while (list1 && list2) {
     13             if (list1->val < list2->val) {
     14                 t = t->next = list1;
     15                 list1 = list1->next;
     16             } else {
     17                 t = t->next = list2;
     18                 list2 = list2->next;
     19             }
     20         }
     21 
     22         t->next = list1 ? list1 : list2;
     23         return head.next;
     24     }
     25 
     26     ListNode *getMid(ListNode *head) {
     27         ListNode *fast, *slow;
     28         fast = slow = head;
     29         while (fast->next && fast->next->next) {
     30             fast = fast->next->next;
     31             slow = slow->next;
     32         }
     33         fast = slow->next;
     34         slow->next = nullptr;
     35         return fast;
     36     }
     37 };