subject ： 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
Program description ：
Method 1 ： First build a dummy node , As a new linked list head, Keep walking and comparing list1 and list2 Node value , Then put it into the new chain list in order . If one of them appears later list It's empty , Just connect the linked list behind it directly to the new linked list . See the picture for details ：（ps： It is a better way to solve the problem of linked list drawing ）
Method 2 ： You will find that method 1 needs to open up a new linked list , This will increase memory space consumption , Therefore, method 2 uses a recursive method , Directly in two list Compare the values in and connect .
All the code ：
Method 1 ：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
phead = ListNode(0)
p = phead
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
if list1 is not None:
p.next = list1
else:
p.next = list2
return phead.next
Method 2 ：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
elif list2 is None:
return list1
elif list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
Title source ： Power button （leetcode）
