148. Sort List

---

My Solution

Solution 1: Top-down Merge Sort

The Key Idea for Solving This Coding Question

C++ Code 1

/**
 * 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) {
        return mergeSort(head);
    }

private:
    ListNode *mergeSort(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *fast = head, *slow = head, *preSlow = nullptr;
        while (fast != nullptr && fast->next != nullptr) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }


        ListNode *head2 = nullptr;
        if (fast != nullptr) {
            head2 = slow->next;
            slow->next = nullptr;
        } else {
            head2 = preSlow->next;
            preSlow->next = nullptr;
        }

        ListNode *left = mergeSort(head);
        ListNode *right = mergeSort(head2);

        return merge(left, right);
    }

    ListNode *merge(ListNode *list1, ListNode *list2) {
        ListNode *dummy = new ListNode(), *it = dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                it->next = list1;
                list1 = list1->next;
            } else {
                it->next = list2;
                list2 = list2->next;
            }
            it = it->next;
        }

        if (list1 != nullptr) {
            it->next = list1;
        } else if (list2 != nullptr) {
            it->next = list2;
        }

        ListNode *sorted = dummy->next;
        delete dummy;
        return sorted;
    }
};

Time Complexity

$O(nlogn)$

$n$ is the length of the linked list.

Space Complexity

$O(logn)$

$n$ is the length of the linked list.

C++ Code 2

/**
 * 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) {
        return mergeSort(head);
    }
    
private:
    ListNode *merge(ListNode *list1, ListNode *list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }
        
        if (list1->val < list2->val) {
            list1->next = merge(list1->next, list2);
            return list1;
        }
        
        list2->next = merge(list1, list2->next);
        return list2;
    }

    ListNode *mergeSort(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode *fast = head, *slow = head, *preSlow = nullptr;
        while (fast && fast->next) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        preSlow->next = nullptr;
        
        ListNode *head1 = mergeSort(head);
        ListNode *head2 = mergeSort(slow);
        ListNode *x = merge(head1, head2);
        
        return x;
    }
};

Solution 2: Buttom-up Merge Sort

The Key Idea for Solving This Coding Question

C++ Code

/**
 * 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 *tail;
    ListNode *nextSubList;
    
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        int n = 0;
        for (ListNode *it = head; it != nullptr; it = it->next) {
            ++n;
        } // end of for-loop
        
        ListNode *start = head;
        ListNode dummyHead(0);
        for (int size = 1; size < n; size = size * 2) {
            tail = &dummyHead;
            while(start) {
                if (start->next == nullptr) {
                    tail->next = start;
                    break;
                }
                ListNode *mid = split(start, size);
                merge(start, mid);
                start = nextSubList;
            } // end of while-loop
            start = dummyHead.next;
        } // end of for loop
        
        return dummyHead.next;
    }
    
    ListNode* split(ListNode *start, int size) {
        ListNode *midPrev = start;
        ListNode *end = start->next;
        for (int index = 1; 
             index <size && (midPrev->next != nullptr || end->next != nullptr); 
             ++index) {
            if (end->next != nullptr) {
                if (end->next->next != nullptr) {
                    end = end->next->next;
                } else {
                    end = end->next;
                }
            }
            if (midPrev->next != nullptr) {
                midPrev = midPrev->next;
            }
        } // end of for-loop
        ListNode *mid = midPrev->next;
        nextSubList = end->next;
        midPrev->next = nullptr;
        end->next = nullptr;
        
        return mid;
    }
    
    void merge(ListNode *list1, ListNode *list2) {
        ListNode dummyHead(0);
        ListNode *newTail = &dummyHead;
        
        while(list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                newTail->next = list1;
                list1 = list1->next;
            } else {
                newTail->next = list2;
                list2 = list2->next;
            }
            newTail = newTail->next;
        } // end of while-loop
        if (list1 != nullptr) {
            newTail->next = list1;
        } else {
            newTail->next = list2;
        }

        while (newTail->next != nullptr) {
            newTail = newTail->next;
        } // end of while
        
        tail->next = dummyHead.next;
        tail = newTail;
        
        return;
    }
};

Time Complexity

$O(nlogn)$

$n$ is the length of the linked list.

Space Complexity

$O(1)$

Miscellaneous