148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.
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) {
        if (head == NULL or head->next == NULL ) return head;
        int length = 0;
        ListNode *p = head;
        while ( p != NULL ) {
            p = p->next;
            length += 1;
        }
        // find the (length/2)th node;
        p = head;
        for ( int i = 1; i <= length/2-1; i++ ) p = p->next;
        ListNode *newp = p->next;
        p->next = NULL;
        ListNode *p1 = sortList(head), *p2 = sortList(newp);
        ListNode *dummy = new ListNode(0);
        p = dummy;
        int i1, i2;
        while ( p1 != NULL or p2 != NULL ) {
            if ( p1 == NULL ) i1 = INT_MAX;
            else i1 = p1->val;
            if ( p2 == NULL ) i2 = INT_MAX;
            else i2 = p2->val;
            if ( i1 < i2 ) { p->next = p1; p1 = p1->next; }
            else { p->next = p2; p2 = p2->next; }
            p = p->next;
        }
        return dummy->next;
    }
};

Notes Merge sort:

• divide into two linked list
• sort each sub-linked list
• merge the two sub-linked lists.