19. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Solution: (Merge Sort)

Algorithm:

img

class Solution
{
public:
    ListNode *findMid(ListNode *head)
    {
        if (head == NULL)
        {
            return head;
        }

        ListNode *p = head;
        ListNode *q = head;
        ListNode *temp = NULL;

        while (p && p->next)
        {
            temp = q;
            q = q->next;
            p = p->next->next;
        }

        if (temp)
        {
            temp->next = NULL;
        }

        return q;
    }

    ListNode *merge(ListNode *p, ListNode *q)
    {
        ListNode *sorted = NULL;
        ListNode *head = NULL;

        if (p == NULL)
        {
            return q;
        }

        if (q == NULL)
        {
            return p;
        }

        if (p->val <= q->val)
        {
            sorted = p;
            p = p->next;
        }
        else if (q->val < p->val)
        {
            sorted = q;
            q = q->next;
        }

        head = sorted;

        while (p && q)
        {
            if (p->val <= q->val)
            {
                sorted->next = p;
                sorted = sorted->next;
                p = p->next;
            }
            else
            {
                sorted->next = q;
                sorted = sorted->next;
                q = q->next;
            }
        }

        if (p == NULL)
        {
            sorted->next = q;
        }
        else
        {
            sorted->next = p;
        }

        return head;
    }

    ListNode *mergeSort(ListNode *head)
    {
     
        if (!head || !head->next)
        {
            return head;
        }

        ListNode *mid = findMid(head);

        ListNode *left = mergeSort(head);
        ListNode *right = mergeSort(mid);
        return merge(left, right);
    }

    ListNode *sortList(ListNode *head)
    {
        return mergeSort(head);
    }
};

Time Complexity: O(nlogn)