148. Sort List - cocoder39/coco39_LC GitHub Wiki

148. Sort List

Notes 2020:

Quicksort is also one of the efficient algorithms with the average time complexity of O(nlogn). But the worst-case time complexity is O(n^2). Also, variations of the quick sort like randomized quicksort are not efficient for the linked list because unlike arrays, random access in the linked list is not possible in O(1) time. If we sort the linked list using quicksort, we would end up using the head as a pivot element which may not be efficient in all scenarios.

Time complexity is O(nlogn) and space complexity is O(log n)

class Solution:
    def sortList(self, head: ListNode) -> ListNode:  
        def merge(list1, list2):
            dummy = ListNode(0)
            p, p1, p2 = dummy, list1, list2
            while p1 and p2:
                if p1.val <= p2.val:
                    p.next = p1
                    p1 = p1.next
                else:
                    p.next = p2
                    p2 = p2.next
                p = p.next
            
            p.next = p1 if p1 else p2
            return dummy.next
            
        def getMidNode(linked_list):
            dummy = ListNode(0)
            dummy.next = linked_list
            
            fast, slow = dummy, dummy
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        if not head or not head.next:
            return head
            
        mid = getMidNode(head)
        second_half = mid.next
        mid.next = None
        first_half = self.sortList(head)
        second_half = self.sortList(second_half)
        return merge(first_half, second_half)

There is also a bottom-up merge-sort approach which consumes O(1) space. Princeton's online CS course:

======================================================================

merge sort O(n * log n)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return mergeSort(head);
    }
private:
    ListNode* mergeSort(ListNode* head){
        if (! head || ! head->next) {// 0/1 element
            return head;
        }
        
        ListNode* part = partition(head);//part == NULL only if head == NULL
        ListNode* head2 = part->next;//assume part != NULL
        part->next = nullptr;
        /* BUG!!!!!!!!
        mergeSort(head);  // return value of merge sort is not equal to input of merge sort
        mergeSort(p); // head of input is not the head of output
        return merge(head, p);
        */
        head = mergeSort(head); 
        head2 = mergeSort(head2);
        return mergeTwoLists(head, head2);;
    }
    
    ListNode* partition(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {//assume (fast=head) != NULL
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* p = &dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        l1 ? p->next = l1 : p->next = l2;
        return dummy.next;
    }
};
⚠️ **GitHub.com Fallback** ⚠️