top145-#148

[LionCoder4ever]

• merge sort
• use fast/slow pointer, get mid node

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL) return head;
        return ms(head, NULL);
    }

    ListNode* ms(ListNode* head, ListNode* tail) {
        if (head->next == tail) {
            head->next = NULL;
            return head;
        }
        ListNode* fast = head, *slow= head;
        while(fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if(fast != tail) fast = fast->next;
        }
        ListNode* ln = ms(head, slow);
        ListNode* rn = ms(slow, tail);
        return reverse(ln, rn);
    }

    ListNode* reverse(ListNode* l, ListNode* r) {
        ListNode head;
        ListNode* cur = &head;
        while(l != NULL && r != NULL) {
            if(l->val < r->val) {
            cur->next = l;
            l = l->next;
        } else {
            cur->next = r;
            r = r->next;
        }
            cur = cur->next;
        }
        if(l != NULL) {
            cur->next= l;
        }
        if(r != NULL) {
            cur->next = r;
        }
        // cur->next = l == NULL ? r : l;
        return head.next;
    }
};