LeetCode 148. Sort linked list

subject

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

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

Tips ：

• The number of nodes in the linked list is in the range  [0, 5 * 104]  Inside
• -105 <= Node.val <= 105

Advanced ： You can  O(n log n)  Under time complexity and constant space complexity , Sort the linked list ？

List sorting , There's still some difficulty , There is such an idea ： First traverse the linked list , Get the number of elements , And then use malloc Apply for the corresponding number of spaces , Store all the linked list elements into the applied array , Using some sort （ Quick line up 、 hill 、 Stack row etc. ） Sort the array , Then write the ordered data back to the linked list .

I don't use the above ideas here , But to operate the linked list directly , So as to achieve the purpose of ordering the linked list . Recursive and non recursive code ideas are merge sorting .

recursive

Ideas

1、 Find the midpoint of the list , With the midpoint as the boundary , Split the linked list into two sub linked lists .

2、 Sort the two sub linked lists separately .

3、 Merge the two sorted sub linked lists , Get the complete sorted linked list .

The above process can be implemented recursively . The termination condition of recursion is that the number of nodes in the linked list is less than or equal to 1, That is, when the linked list is empty or the linked list only contains 1 When a node , There is no need to split and sort the linked list .

To find the midpoint of the linked list, you can use the fast and slow pointer , Every time the fast pointer moves 2 Step , Each time the slow pointer moves 1  Step , When the fast pointer reaches the end of the linked list , The linked list node pointed to by the slow pointer is the midpoint of the linked list .

The method of tail insertion can be used to merge two linked lists , Insert the node endlessly after the given header .

Code

struct ListNode* Mergedata(struct ListNode* head1,struct ListNode* head2){// Merge two ordered lists 
    struct ListNode s;// Given the chain header 
    struct ListNode* cur=&s;// The head pointer , Point to the head of the chain 
    while(head1&&head2){// Insert the tail of two ordered linked lists into s after 
        if(head1->val<=head2->val){
            cur->next=head1;
            head1=head1->next;
        }else{
            cur->next=head2;
            head2=head2->next;
        }
        cur=cur->next;
    }
    if(head1){// Tail the rest 
        cur->next=head1;
    }else{
        cur->next=head2;
    }
    return s.next;
}
struct ListNode* Middle(struct ListNode* head){
    // Find the middle node of the linked list , And return the address , Note that this function will divide a linked list into two .
    struct ListNode* prev=NULL;
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next){
        prev=slow;
        slow=slow->next;
        fast=fast->next->next;
    }
    prev->next=NULL;
    return slow;
}
struct ListNode* sortList(struct ListNode* head){
    if(head==NULL||head->next==NULL){
        return head;
    }
    struct ListNode* cur=Middle(head);// Get the address of the intermediate node 
    head=sortList(head);// Put the first half in order 
    cur=sortList(cur);// Put the second half in order 
    return Mergedata(head,cur);// Merge the two parts 
}

 

After reading the above code , Using recursion , You will find that this problem is actually ： Merge two ordered lists 、 Find the middle node of the list 、 Merge sort The fusion of these three questions .

Complexity analysis

Time complexity ： Merge sort , The time complexity is O(NlogN).

Spatial complexity ： The recursion depth is logN, So the space complexity is zero O(logN).

Non recursive

Because the space complexity of the advanced problem is O(1), Obviously, the above recursive code does not meet the requirements . At this point, we need to find a way to turn recursion into a loop .

Ideas

First, find the length of the linked list len, Then split the linked list into sub linked lists and merge them .

The specific methods are as follows ：

1、 use step Indicates the length of the sub linked list to be sorted each time , At the beginning step=1;

2、 Split the linked list into several at a time, with a length of step A child of the linked list （ The length of the last sub linked list can be less than step）, Merge according to every two sub linked lists , After merging, you can get several pieces with a length of 2*step Ordered sub linked list （ The length of the last sub linked list can be less than 2*step）.

3、 take step Double the value of , Repeat the first 2 Step , Merge the longer ordered sub linked list , Until the length of the ordered sub linked list is greater than or equal to len, The whole linked list is sorted .

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* Mergedata(struct ListNode* head1,struct ListNode* head2){// Merge two ordered lists 
    struct ListNode s;
    struct ListNode* cur=&s;
    while(head1&&head2){
        if(head1->val<=head2->val){
            cur->next=head1;
            head1=head1->next;
        }else{
            cur->next=head2;
            head2=head2->next;
        }
        cur=cur->next;
    }
    if(head1){
        cur->next=head1;
    }else{
        cur->next=head2;
    }
    return s.next;
}
struct ListNode* Disconnect(struct ListNode* head,int step){
    // Link the list according to step Length split , And return the address of the remaining part after splitting 
    if(head==NULL){
        return NULL;
    }
    struct ListNode* cur=head;
    for(int i=0;head&&i<step;i++){
        cur=head;
        head=head->next;
    }
    cur->next=NULL;
    return head;
}
int Length(struct ListNode* head){// Find the length of the list 
    int count=0;
    while(head){
        head=head->next;
        count++;
    }
    return count;
}
struct ListNode* sortList(struct ListNode* head){
    struct ListNode s;// Given the header node , Convenient tail insertion 
    struct ListNode* cur=&s;// Point to the given header node 
    cur->next=head;// First connect the given linked list , This step must be done 
    int len=Length(head);
    for(int step=1;step<len;step*=2){//step<len, Merge and sort continue 
        head=s.next;// to update head
        cur=&s;// to update cur
        while(head){// Every time step In groups , To carry on the merge , until head It's empty 
            struct ListNode* h1=head;// Get the first part after the split 
            struct ListNode* h2=Disconnect(h1,step);// Get the second part after the split 
            head=Disconnect(h2,step);// Get the rest after splitting 
            cur->next=Mergedata(h1,h2);// Merge the first and second parts , And inserted at the end s after 
            while(cur->next){//cur Go straight ahead , Convenient for the next tail insertion 
                cur=cur->next;
            }
        }
    }
    return s.next;
}

  Complexity analysis

Time complexity ： Merge sort , The time complexity is O(NlogN).

Spatial complexity ： No extra space requested , The space complexity is O(1).