leetcode Question: Sort List

leetcode Question: Sort List

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

Analysis:

From the post "Common Sorting Algorithms", we know that the sorting algorithms which have O(n log n) complexity are merge sort and quick sort. So in this problem, we can use merge sort to handle!

Different from array data, this problem requires good understanding of linked list operations, e.g., split, merge.  Before doing this problem, I suggest you first check out the problem "Merge Two Sorted List" and "Linked List Cycle", and also the merge sort algorithm itself. Then the problem becomes pretty straightforward.

Like the merge sort, we can do recursively:
(1) Split the list (slow fast pointers)
(2) sort the first part (merge sort)
(3) sort the second part (merge sort)
(4) merge the two parts (merge two sorted lists)

See the code below for details. In this code, the pointer to the pointer (reference pointer) is used, note that to get the pointer where "ptrRef" points, we can use "*ptrRef".

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // Merge two sorted list (save as the leetcode Question 54: Merge Two Sorted Lists)
    ListNode* sortedMerge(ListNode* l1, ListNode* l2){
        ListNode* res = new ListNode(0);
        ListNode* current = res;
        while (true){
            if (!l1){
                current->next = l2;
                break;
            }
            if (!l2){
                current->next = l1;
                break;
            }
            if (l1->val < l2->val){
                current->next = l1;
                l1 = l1->next;
            }else{
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        return res->next;
    }

    // Split a list into two parts, using slow/fast pointers
    void split(ListNode* head, ListNode** aRef, ListNode** bRef){
        ListNode* slow;
        ListNode* fast;
        if (head==NULL || head->next==NULL){
            *aRef = head;
            *bRef = NULL;
        }else{
            slow = head;
            fast = head;
            while (fast!=NULL && fast->next!=NULL){
                fast = fast->next->next;
                if (fast==NULL){break;} // this is important
                slow = slow->next;
            }
            *aRef = head;
            *bRef = slow->next;
            slow->next=NULL;
        }
    }

    // MergeSort LinkedList
    void mergeSort(ListNode** headRef){
        ListNode* head = *headRef;
        ListNode* a;
        ListNode* b;
        
        if (head==NULL || head->next==NULL){
            return;
        }
        
        split(head,&a,&b);   //split the list
        
        mergeSort(&a);       //sort the first part
        mergeSort(&b);       //sort the second part    
        
        *headRef = sortedMerge(a,b);    // merge two sorted part
    }

    //main function
    ListNode *sortList(ListNode *head) {
        mergeSort(&head);
        return head;
    }
};