Sort List

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

tag: list, sort

9/22/2015 update

a cleaner solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //base condition
       if(head == NULL || head->next == NULL) return head;
       
       ListNode * mid = splitList(head);
       mid = sortList(mid);
       head = sortList(head);
       
       //merge two sorted list
       ListNode dummyHead = ListNode(0);
       ListNode *tail = &dummyHead;
       while(mid != NULL && head != NULL){
           ListNode * &p = mid->val < head->val? mid: head;
           tail->next = p;
           tail = tail->next;
           p = p->next;
       }
       tail->next = mid == NULL? head: mid;
       return dummyHead.next;
    }
    //split the list evenly
    ListNode * splitList(ListNode * head){
        ListNode * fast, * slow, * prev;
        fast = slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        prev->next = NULL;
        return slow;
    }
};

想到了归并排序(merge sort)，但是在犹豫寻找list的中点的额外开销。因为数组的话可以直接利用下标(start + end) / 2来获取中点，list的话必须用N/2的时间遍历到中点。怕这样的时间开销会让最终的结果超过o(nlogn)。

实际是我多虑了。

对于 T(N) = 2T(N/2) + N 的递推式，最终的时间开销是o(nlogn)

在本题中， T(N) = 2T(N/2) + N/2 + N。最终的时间开销也是o(nlogn)，在一个量级上。

找到List的中点，可以用fast-slow指针法。定义两个指针，一个指针每次走两步，另一个指针每次走一步。这样当快指针走到结尾时，慢指针正好走到中间。

然后对于分成两半的list，先sort，再merge。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        else{
            ListNode * fast, * slow, * prev;
            fast = slow = head;
            //split list into two parts
            while(fast != NULL && fast->next != NULL){
                fast = fast->next->next;
                prev = slow;
                slow = slow->next;
            }
            prev->next = NULL;
            ListNode * leftPart = head;
            ListNode * rightPart = slow;
            ListNode * sortedLeftPart = sortList(leftPart);
            ListNode * sortedRightPart = sortList(rightPart);
            return merge(sortedLeftPart, sortedRightPart);
        }
    }
    ListNode * merge(ListNode * left, ListNode * right){
        ListNode * superHead = new ListNode(0);
        ListNode * head = superHead;
        ListNode * p = head;
        while(left && right){
            if(left->val < right->val){
                p->next = left;
                left = left->next;
            }
            else{
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
        if(left){
            p->next = left;
        }
        if(right){
            p->next = right;
        }
        head = superHead->next;
        superHead->next = NULL;
        delete superHead;
        return head;
    }
};