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($nlog_2n$) 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 * 10^4$].
  • $-10^5$ <= Node.val <= $10^5$

5. Solutions

My Accepted Solution

n is the number of nodes in the m_head
Time complexity: O($n^2$)
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($nlog_2n$)
Space complexity: O($log_2n$)

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($nlog_2n$)
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;
    }
};
comments powered by Disqus