Leetcode learn to insert and sort unordered linked lists (detailed explanation)

Preface

Please have a seat

One 、 Insert the sorting question link into the unordered linked list

Title Description

Insert and sort the linked list .

Insertion sort algorithm ：

1. The insertion sort is iterative , Move only one element at a time , Until all elements can form an ordered output list .
2. In each iteration , Insert sort removes only one element to be sorted from the input data , Find its place in the sequence , And insert it into .
3. Repeat until all input data is inserted .

The test sample 1：

Input : 4->2->1->3
Output : 1->2->3->4

The test sample 2：

Input : -1->5->3->4->0
Output : -1->0->3->4->5

Topic ideas

Rearrange the list

1. Remove the first node , And put the next empty , Prevent the formation of circular linked list
2. Then define several pointers to operate , Compare c and cur
3. If cur->val Greater than c->val, be c and p All in one , Otherwise start sorting
   Pictured :
   
4. One Always pay attention newhead->val Value , To compare newhead->val The value of and cur->val, If newhead->val<=cur->val, Then let newhead Point to cur, Guarantee newhead Always point to the head node . Two There's another way to write it , Observe the law , Only when p yes NULL It's time to change newhead, So it can be used p Is it NULL To change newhead.
   Pictured :
   
5. You have to judge p Is it NULL When , If the first comparison ,cur->val Less than c->val, be p No change required .

Be careful ： Because it's out of order , So pay attention to newhead The direction of , To put newhead Always point to the head node .

There are two kinds of code , Different styles

Code 1

The code is as follows : This is the solution of not creating sentinel positions , Of course, this is to insert in the second loop

struct ListNode* insertionSortList(struct ListNode* head)
{
    
    if(head==NULL||head->next==NULL)
    {
    
        return head;
    }
    //1
    struct ListNode*newhead=head;
    struct ListNode*cur=head->next;
    newhead->next=NULL;

    //2
    while(cur)// Termination conditions 
    {
    
        struct ListNode* next=cur->next;
        struct ListNode* c=newhead;
        struct ListNode* p=NULL;

        while(c)
        {
          
            if(cur->val<=c->val)
            {
    
                // Determine the head node 
                if(newhead->val>=cur->val)
                {
    
                    newhead=cur;
                }
                // Judge p
                if(p!=NULL)
                {
    
                  p->next=cur;
                   
                }                                  
                cur->next=c;                
                break;               
            }
            else
            {
    
                p=c;
                c=c->next;
            }
            
        }

        if(c==NULL)
        {
    
            p->next=cur;
            cur->next=c;
            

        }

        cur=next;
        

    }
    
    return newhead;
}

Code 2

The code is as follows : This is the solution to create sentinel positions , Of course, this is in the second loop to insert

typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head){
    
  if(head == NULL || head->next == NULL)
    return head;
  // Create a sort linked list 
  Node* sortHead = (Node*)malloc(sizeof(Node));
  // The head node is inserted first 
  sortHead->next = head;
  head = head->next;
  sortHead->next->next = NULL;
  // Insert remaining nodes 
  Node* cur = head;
  while(cur)
  {
    
    // First save next node 
    Node* next = cur->next;
 
    //  Start from the head of the sorting linked list , Find a suitable location for the node to be inserted 
    Node* sortPrev = sortHead;
    Node* sortCur = sortHead->next;
     
    while(sortCur)
    {
    
      if(cur->val > sortCur->val)
      {
    
        sortPrev = sortCur;
        sortCur = sortCur->next;
      }
      else
      {
    
        break;
      }
    }
    // Insert in place 
    sortPrev->next = cur;
    cur->next = sortCur;
 
    cur = next;
  }
 
  Node* sortList = sortHead->next;
  free(sortHead);
 
  return sortList; 
}
 

summary

This question is to think comprehensively , Then write patiently and slowly