leetcode

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 };