leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0148.cpp (991B)

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