题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
解题
方法一：递归
# 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, l1, l2): if l1 is None: return l2 elif l2 is None: return l1 elif l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
方法二：迭代
创建一个新的节点，将两个链表的节点依次比较，小的则加入到新的链表后。最后l1和l2至少有一个是空了，那么把不空的l1或l2,全部添加在新链表后面就行了。
# 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, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode() cur = dummy while l1 and l2: if l1.val<=l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 is not None else l2 return dummy.next
另外一种写法
# 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, l1: ListNode, l2: ListNode) -> ListNode: dummy = curr = ListNode() while l1 or l2: if not l1: curr.next = l2 break if not l2: curr.next = l1 break if l1.val<l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next return dummy.next
