Li Kou 148: sorting linked list

Power button 148： Sort list

Title Description

Here's the head of the list head , Please press Ascending Arrange and return to Sorted list .

I/o sample

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

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

 Input ：head = []
 Output ：[]

Solution 1 , Merge sort using recursion , The top-down , The space complexity is O(logN)

class Solution
{
    
public:
ListNode *sortList(ListNode *head)
{
    
    return sortListNode(head,nullptr); 
}

ListNode *sortListNode(ListNode *head,ListNode *tail)
{
    
    if(head==nullptr)
    {
    
        return head;
    }

    if(head->next==tail)
    {
    
        head->next=nullptr;
        return head;
    }




    ListNode*slow=head;
    ListNode*fast=head;

    // Look for the midpoint of the list 
    while(fast!=tail)
    {
    
        slow=slow->next;
        fast=fast->next;
        if(fast!=tail)
        {
    
            fast=fast->next;
        }

    }
    ListNode *mid=slow;
// Always recursively merge 
    return merge(sortListNode(head,mid),sortListNode(mid,tail));
}

ListNode *merge(ListNode*head1,ListNode*head2)
{
    
    // Establish dummy node 
    ListNode *dummyHead=new ListNode(0);
    ListNode *temp=dummyHead;
    ListNode *temp1=head1;
    ListNode *temp2=head2;

    while(temp1!=nullptr&&temp2!=nullptr)
    {
    
        if(temp1->val<=temp2->val)
        {
    
            temp->next=temp1;
            temp1=temp1->next;
        }
        else{
    
            temp->next=temp2;
            temp2=temp2->next;
        }
        temp=temp->next;
    }

    if(temp1!=nullptr)
    {
    
        temp->next=temp1;
    }
   else if(temp2!=nullptr)
    {
    
        temp->next=temp2;
    }
    return dummyHead->next;

}
};

Solution 2 , Use non recursive merge sort , Top down Algorithm , Spatial complexity O(1)

// Use bottom-up merge sort 
// In a non recursive way 

// First, you need to get the length of the linked list 

//sublength  Indicates the length of the sub linked list to be sorted each time 
// Split the list into several lengths subLength A child of the linked list , Merge according to every two sub linked lists , Get several strings , Then continue to merge according to the algorithm 

class Solution2
{
    
public:
    ListNode *sortList(ListNode *head)
    {
    
        if(head==nullptr)
        {
    
            return head;
        }

        int length=0;
        ListNode *node=head;
        // Get the length of the list 
        while(node!=nullptr)
        {
    
            length++;
            node=node->next;
        }

        // Create a dummy node 
        ListNode *dummyHead=new ListNode(0,head);
        //sublength<<=1  amount to subLength=sublength*2
        for(int subLength=1;subLength<length;subLength<<=1)
        {
    
            // First, set the node point 
            //prev Point to the dummy node 
            //curr Point to the given linked list 
            ListNode *prev=dummyHead;
            ListNode *curr=dummyHead->next;

            while(curr!=nullptr)
            {
    //head1 It refers to the first node to be connected 
                ListNode *head1=curr;

                for(int i=1;i<subLength&&curr->next!=nullptr;i++)
                {
    
                    curr=curr->next;
                }
            //head2 Point to the second child node to be connected 
                ListNode *head2=curr->next;

                // This way curr->next=nullptr  Is making  header1  No other nodes will be connected later 
                curr->next=nullptr;
                // send curr Point back to head2 node , Skippable head1
                curr=head2;

                for(int i=1;i<subLength&&curr!=nullptr&&curr->next!=nullptr;i++)
                {
    
                    curr=curr->next;
                }

                ListNode *next=nullptr;
                if(curr!=nullptr)
                {
    
                    // Here, too, let  next preservation head2 The node after , And will head2 The next node is set to nullptr
                    next=curr->next;
                    curr->next=nullptr;
                }

                // Merge two lists , And use prev Point to 
                ListNode *merged=merge(head1,head2);
                prev->next=merged;

                // send prev Point to the end of the linked list 
                while(prev->next!=nullptr)
                {
    
                    prev=prev->next;
                }
                // Here we will deal with the next two together 
                curr=next;
            }
        }
        return dummyHead->next;
    }

    ListNode *merge(ListNode*head1,ListNode*head2)
    {
    
        // Establish dummy node 
        ListNode *dummyHead=new ListNode(0);
        ListNode *temp=dummyHead;
        ListNode *temp1=head1;
        ListNode *temp2=head2;

        while(temp1!=nullptr&&temp2!=nullptr)
        {
    
            if(temp1->val<=temp2->val)
            {
    
                temp->next=temp1;
                temp1=temp1->next;
            }
            else{
    
                temp->next=temp2;
                temp2=temp2->next;
            }
            temp=temp->next;
        }

        if(temp1!=nullptr)
        {
    
            temp->next=temp1;
        }
    else if(temp2!=nullptr)
        {
    
            temp->next=temp2;
        }
        return dummyHead->next;

    }
};