leetCode The first 21 topic Merge two ordered lists
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
about python3 The linked list of , There is a hint in the title
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
We know that the linked list contains two elements , One is int Type val（ The default value is 0）, The other is next, Used to point to the next node , So it should be ListNode type
The way of double pointer plus loop can be adopted for thinking
l1 and l2 It's two linked lists , But the essence is the head pointer of the linked list , So just use it as a pointer , There is no need to define a new pointer
Compare l1 and l2 Value , If l1 Than l2 Small , It will be p.next Point to l1, then l1 Move backward (l1 = l1.next); otherwise p.next Point to l2,l2 Move backward
As long as a table is traversed first , namely l = None, Then exit the loop , Put the table that has not been traversed directly in p After the tail of the
Consider special circumstances , If l1(l2) At the beginning, it was an empty table , Then go straight back l2(l1).
The loop only iterates through the two tables , The time complexity is O(m+n)
## python3
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None: # l1 Empty to return directly to l2
return l2
if l2 == None: # l2 Empty to return directly to l1
return l1
result = ListNode() # Store results
p = result # The pointer
while l1 != None and l2 != None:
if l1.val < l2.val: # Compare the values of two nodes ,l1 The value of is small
p.next = l1 # take p The next node of points to the current l1
l1 = l1.next # l1 Move backward
else: # Otherwise it would be p The next of points to the current l2,l2 Then move back
p.next = l2
l2 = l2.next
p = p.next
if l1 != None: # If l1 Not finished traversing , Directly in p Followed by the rest of
p.next = l1
if l2 != None:
p.next = l2
return result.next
Continue the analysis , You can use recursion to operate
When p Pointing to l1 When the header node of , The problem becomes l1.next and l2 Merge two ordered linked lists , The scale of the problem has become smaller , But the problem is the merging of linked lists , This means that you can use recursion , The code is as follows .
## python3
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None: # l1 Empty to return directly to l2
return l2
if l2 == None: # l2 Empty to return directly to l1
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
