Leetcode daily practice - 21. Merge two ordered linked lists

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 21. Merge two ordered lists

Let’s get it！

---

---

1. Topic analysis

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：

Example 2：

Example 3：

2. Title diagram

This question is actually Merger Ideas , Take the smaller node each time Tail insertion To the new linked list

Train of thought

Define pointer list 1 Point to the first linked list Head node , Define pointer list 2 Point to the second linked list Head node ;

Define a new linked list , At this point, the head node head and Tail node tail All for NULL, As shown in the figure

Let's analyze Tail insertion The process of ：

The first 1 Time , When list 1 be equal to list 2 when , Just put list 1 Insert into the new linked list , to head and tail;

The first 2 Time , When list 2 Less than list 1 when , Just put list 2 Insert into the new linked list , to update tail;

The first 3 Time , When list 1 Less than list 2 when , Just put list 1 Insert into the new linked list , to update tail;

Here you can see the dynamic diagram demonstration directly

Be careful ：

When any one of the linked lists points to NULL when , Put the remaining elements of the linked list directly Copy To the new linked list .
 
such as ,list 1 Point first NULL, So directly put list 2 Get the remaining elements New linked list in , There is no need to update tail 了 , Directly return to the new linked list Head node .

Why not update tail Well ？

What we are going back to is Head node , There is no need to return to the new Tail node , What is defined here tail Just convenient Tail insertion .

Interface code

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    if (list1 == NULL) {
    
        return list2;
    }
    if (list2 == NULL) {
    
        return list1;
    }
    struct ListNode* head = NULL, *tail = NULL;
    while (list1 && list2) {
    
    	// list1  Less than  list2
        if ((list1->val) < (list2->val)) {
    
            if (tail == NULL) {
    
                head = tail = list1;
            }
            else {
    
                tail->next = list1;
                tail = list1;
                // tail = tail->next
            }
            list1 = list1->next;
        }
        // list1  Greater than or equal to  list2
        else {
    
            if (tail == NULL) {
    
                head = tail = list2;
            }
            else {
    
                tail->next = list2;
                tail = list2;
                // tail = tail->next
            }
            list2 = list2->next;
        }
    }
    if (list1) {
    
        tail->next = list1;
    }
    if (list2) {
    
        tail->next = list2;
    }
    return head;
}

Submit results

Train of thought

We can build a new Leading node New linked list of , That is to say Sentry post The head node of , This node does not store valid data .

So this Take the lead and Don't take the lead What's the difference ？

stay Train of thought in , The new linked list we defined does not take the lead ,head and tail All point to NULL, So at insertion , To judge ,tail Is it NULL The situation of .
 
So if I set one Sentry post The head node of , Then there is no need to judge , Even if there is no value at this time ,head and tail It's impossible for empty , So it's going on Tail insertion when , Insert the element directly into Sentry post Just behind .

Principle or and Train of thought It's the same , So look directly at the motion chart

Be careful ：

On return , Can't return head, It's going back to head Point to the next, That is to say Sentry post The next node of ;
 
Because the two linked lists given in the title do not have sentinel positions , So after our merger , Those who return are also without sentry positions

Interface code

//  Single linked list of leading nodes 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode* head = NULL, *tail = NULL;

    //  Set up a sentry post 
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;

    while (list1  && list2) {
    
        if ((list1->val) < (list2->val)) {
    
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else {
    
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if (list1) {
    
        tail->next = list1;
    }
    if (list2) {
    
        tail->next = list2;
    }

    //  Release 
    struct ListNode* list = head->next;
    free(head);
    return list;
}

Submit results