[record of question brushing] 21. Merge two ordered linked lists

One 、 Title Description

source ：

Power button （LeetCode）

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]


Tips ：

• The range of the number of nodes in the two linked lists is  [0, 50]

• -100 <= Node.val <= 100

• l1  and  l2  All according to   Non decreasing order   array

II. Train of thought analysis

Double pointer solution

This question is similar  

【 Record of writing questions 】2.  Addition of two numbers

  In the last question , Is to give two linked lists , Add the numbers in the node in turn , Compose a new linked list , And in this question , Direct comparison (

because l1  and  l2  All according to   Non decreasing order   array

) The values of the nodes in the two linked lists , Synthesize a new linked list .

3、 ... and 、 Code implementation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 ListNode dummy = new ListNode(-1);

 ListNode prev = dummy;
 while (l1 != null && l2 != null) {
 if (l1.val <= l2.val) {
 prev.next = l1;
 l1 = l1.next;
 } else {
 prev.next = l2;
 l2 = l2.next;
 }
 prev = prev.next;
 }

 //  If there is a linked list that has not been traversed
 prev.next = l1 == null ? l2 : l1;

 return dummy.next;
 }
}


Complexity analysis

• Time complexity ： Scan two linked lists . The complexity is &nbsp;
  
  
   
  m
  ,
  n
  For the length of two linked lists

• Spatial complexity ：
  
  

Running results

summary

This problem is also a deformation problem that deals with linked lists through double pointers . Understand this idea , We can use this in many places to help us deal with the corresponding problems .

Continue refueling ~