Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Merge two ordered lists

I. Title Description:

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example 1:

Input: l1 = 4-trichlorobenzene [1], l2 = [1 4] output:,1,2,3,4,4 [1] example 2:

Input: L1 = [], L2 = [] Output: [] Example 3:

Input: L1 = [], L2 = [0] output: [0]

Tip:

The number of nodes in both lists ranges from [0, 50] -100 <= node. val <= 100, both L1 and L2 are in non-descending order

Ii. Analysis of Ideas:

  1. What ideas does this question examine? What’s your thinking?

    This topic is the basic operation of linked lists, merging two ordered linked lists. My idea is to use recursion to complete the merge.

    We can have mergeTwoLists(list1->next, list2) because list1 = mergeTwoLists(list1, list2).

  2. Did you pass the problem at the first time? What problems did you encounter? What details should you pay attention to?

    This topic is relatively easy as long as you clear your mind. Be careful not to be careless. Note that if the list started as an empty list, you simply return the non-empty list without doing anything.

  3. There are several solutions, which one has the least time complexity, which one has the least space complexity, and what is the optimal solution? What are other people’s problems? Who’s more efficient? Which language is the fastest to implement in different languages?

    But using recursion takes a lot of space, so space complexity is a little bit higher.

    Here’s another idea:

Iii. AC Code:

 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
 ​
 ​
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
 {
     if(list1 == NULL)
         return list2;
     else if(list2 == NULL)
         return list1;
     else if(list1->val < list2->val)
     {
         list1->next = mergeTwoLists(list1->next, list2);
         return list1;
     }
     else
     {
         list2->next = mergeTwoLists(list1, list2->next);
         returnlist2; }}Copy the code

 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
 ​
 ​
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
 {
     struct ListNode* h, *p;
     h=(struct ListNode*)malloc(sizeof(struct ListNode));
     p=h;
     while(list1 && list2)
     {
         if(list1->val <= list2->val)
         {
             h->next=list1;
             list1=list1->next;
         }
         else{ h->next=list2; list2=list2->next; } h=h->next; } h->next=list1? list1:list2;return p->next;
 }
 ​
 ​
Copy the code

Iv. Summary:

The basic operation of the linked list must be mastered!