[leetcode]148. Sort List

Problem
Sort a linked list in O(n log n) time using constant space complexity.

Solution

 MergeSort.

Code

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode *h1 = sortList(head);
        ListNode *h2 = sortList(fast);
        return Merge(h1,h2);
    }
    
    ListNode* Merge(ListNode* h1,ListNode* h2) {
        ListNode *head = new ListNode(0);
        ListNode *tail = head;
        while (h1 || h2) {
            if (h1 && h2) {
                if (h1->val < h2->val) {
                    tail->next = h1;
                    h1 = h1->next;
                    tail = tail->next;
                }
                else {
                    tail->next = h2;
                    h2 = h2->next;
                    tail = tail->next;
                }
            }
            else {
                if (h1) {
                    tail->next = h1;
                    h1 = h1->next;
                    tail = tail->next;
                }
                if (h2) {
                    tail->next = h2;
                    h2 = h2->next;
                    tail = tail->next;
                }
            }
        }
        return head->next;
    }
};