[leetcode ladder] linked list · 021 merge two ordered linked lists

Title Description ：

Merge two ascending linked lists into a new   Ascending   Link list and return . The new linked list is made up of all the nodes of the given two linked lists . 

Example 1：

 Input ：l1 = [1,2,4], l2 = [1,3,4]
 Output ：[1,1,2,3,4,4]

Example 2：

 Input ：l1 = [], l2 = []
 Output ：[]

Example 3：

 Input ：l1 = [], l2 = [0]
 Output ：[0]

Topic link ：

21. Merge two ordered lists - Power button （LeetCode）https://leetcode.cn/problems/merge-two-sorted-lists/

---

Their thinking ：

Conventional method 1： Create a new linked list to receive  

I think this method should be the most basic approach , Use four pointers to operate , Two pointers are used to traverse the original linked list , A pointer is used to identify the header of the new linked list , Another pointer is used to identify the end of the new linked list , Facilitate the tail insertion of new nodes .

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode*n1=list1; //n1 Pointers are used to traverse list1
    struct ListNode*n2=list2; //n2 Pointers are used to traverse list2
    struct ListNode*newHead=NULL; 
    struct ListNode*tail=NULL;
    while(n1&&n2) // When n1 or n2 There is one for NULL Jump out of the loop 
    {
        if(n1->val<=n2->val) // When n1 The value of the node pointed to is less than or equal to n2 after 
        {
            if(newHead==NULL) // When the new linked list is empty 
            {
                newHead=n1; // take n1 As the head node of the new linked list 
                tail=n1;
                n1=n1->next;
            }
            else // When the new linked list is not empty 
            {
                tail->next=n1; // Connect the tail node of the new linked list to n1
                tail=n1;
                n1=n1->next;
            } 
        }
        else // When n1 The node value pointed to is greater than n2 when 
        {
            if(newHead==NULL) // When the new linked list is empty 
            {
                newHead=n2; // take n2 As the head node of the new linked list 
                tail=n2;
                n2=n2->next;
            }
            else // When the new linked list is not empty 
            {
                tail->next=n2; // Connect the tail node of the new linked list to n1
                tail=n2;
                n2=n2->next;
            }    
        }
    }
    if(newHead==NULL) // It shows that a linked list is empty at the beginning 
    {
        if(n1==NULL)
            return n2;
        else if(n2==NULL)
            return n1;
        else if(n1==NULL&&n2==NULL)
            return NULL;
    }
    if(n1==NULL)
        tail->next=n2;
    if(n2==NULL)
        tail->next=n1;
    return newHead; 
}

To sum up ： We found that this problem is slightly longer , It is because we need to discuss that the new chain header pointer may or may not be empty , For the problem that the head node of the new linked list may be empty , We must be here 【 Remove linked list elements 】 It has been introduced in this sentence , Using sentinel method can greatly simplify the above code .

Conventional method 2： Sentinel law

To simplify the above operation , In addition to establishing a sentry post , In fact, we only need to set two pointers ,n1 and n2 The pointer can use the original list1 and list2 To replace , Because of the result of this problem, we don't need to return to the original linked list , Just return a new merged linked list .

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* newHead=NULL,*tail=NULL;
    newHead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));// At first tail and newHead Point to the same dynamic node space 
    while(list1&&list2) // When list1 or list2 There is a null jump out of the loop 
    {
        if(list1->val<=list2->val)
        {
            if(tail==NULL) // When the new linked list is empty 
            {
                newHead->next=tail=list1; // take list1 The node pointed to is linked after the sentinel 
            }
            else // When the new linked list is not empty 
            {
                tail->next=list1; // take list1 The node pointed to is directly linked after the new linked list 
                tail=list1;
            }
            list1=list1->next; //list1 Take a step back 
        }
        else
        {
            if(tail==NULL)
            {
                newHead->next=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }    
    }
    if(list1==NULL)
        tail->next=list2;
    if(list2==NULL)
        tail->next=list1;
    struct ListNode* list=newHead->next; // Define a list The pointer points after the sentinel node 
    free(newHead); //free Drop the sentinel node 
    return list;
}

To sum up ： The cleverness of using sentinel method here is that it will tail and newHead All point to the same sentinel node space . For example, when there is a list It's empty time , Cannot enter at this time while loop , But you can enter with while The program that jumps out after the loop shares the same piece of code , Without classified discussion , This is because at first tail and newHead It points to the same sentinel node space , So for those programs that don't enter the loop , Their execution tail->next=list1, It's equivalent to executing newHead->next=list1. Eventually they and those enter while The procedure of the loop is the same , Finally, share one return newHead->next Statement can realize output operation .