148. Sort List

Posted on 3 mins read

1. Description

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

2. Follow Up

Can you sort the linked list in O(nlog2n) time and O(1) memory (i.e. constant space)?

3. Example

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: []

4. Constraints

  • The number of nodes in the list is in the range [0, 5∗104].
  • −105 <= Node.val <= 105

5. Solutions

My Accepted Solution

n is the number of nodes in the m_head
Time complexity: O(n2)
Space complexity: O(1)

// insertion sort: Time Limit Exceeded

5.1 Merge Sort Top to Down

n is the number of nodes in the m_head
Time complexity: O(nlog2n)
Space complexity: O(log2n)

class Solution 
{
private:
    ListNode* merge(ListNode* m_list1, ListNode* m_list2)
    {
        ListNode head(0);
        ListNode *tail = &head;

        while(m_list1 && m_list2) // m_list1 is the lowwer list
        {
            if(m_list1->val > m_list2->val) swap(m_list1, m_list2);

            tail->next = m_list1;
            m_list1 = m_list1->next;
            tail = tail->next;
        }

        tail->next = m_list1 ? m_list1 : m_list2;

        return head.next;
    }

    ListNode* findMiddleNode(ListNode* i_head)
    {
        auto slow = i_head;
        for(auto fast = i_head->next; fast && fast->next; )
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        auto result = slow->next;
        slow->next = nullptr;
        return result;
    }
public:
    // ListNode* sortList(ListNode* head)
    ListNode* sortList(ListNode* m_head) 
    {
        if(!m_head || !m_head->next) return m_head;

        auto mid = findMiddleNode(m_head);
        return merge(sortList(m_head), sortList(mid));
    }
};

5.2 Merge Sort Down to Top(Follow Up)

n is the number of nodes in the m_head
Time complexity: O(nlog2n)
Space complexity: O(2)

class Solution 
{
private:
    // split the list into two parts, the first part has m_count nodes
    // return the head of the rest part
    ListNode* split(ListNode* m_head, int m_count)
    {
        while(--m_count && m_head)
        {
            m_head = m_head->next;
        }

        auto rest = (m_head ? m_head->next : nullptr);

        if(m_head) m_head->next = nullptr;

        return rest;
    }

    // merge two lists and return the head and tail of the merged list
    pair<ListNode*, ListNode*> merge(ListNode* m_list1, ListNode* m_list2)
    {
        ListNode head(0);
        ListNode *tail = &head;

        while(m_list1 && m_list2)
        {
            if(m_list1->val > m_list2->val) swap(m_list1, m_list2);

            tail->next = m_list1;
            m_list1 = m_list1->next;
            tail = tail->next;
        }

        tail->next = (m_list1 ? m_list1 : m_list2);

        while(tail->next) tail = tail->next;

        return {head.next, tail};
    }
public:
    // ListNode* sortList(ListNode* head)
    ListNode* sortList(ListNode* m_head) 
    {
        if(!m_head || !m_head->next) return m_head;

        int nodesCount = 1;
        for(auto iter = m_head; iter; iter = iter->next) 
        {
            nodesCount++;
        }

        ListNode head(0);
        head.next = m_head;
        ListNode *left, *right, *tail;
        for(int i = 1; i < nodesCount; i = i << 1)
        {
            auto current = head.next;
            tail = &head;
            while(current)
            {
                left = current;
                right = split(left, i);
                
                current = split(right, i);
                auto mergedList = merge(left, right);
                tail->next = mergedList.first;
                tail = mergedList.second;
            }
        }

        return head.next;
    }
};