題目描述
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的生音。
image.png
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
解法一
挨個比較脉让，最后將多出來的追加末尾
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = res = ListNode() # 虛擬頭結(jié)點
# 挨個比較
while l1 and l2:
if l1.val > l2.val:
cur.next = l2
l2 = l2.next
else:
cur.next = l1
l1 = l1.next
cur = cur.next
# 將兩個鏈表中未比較的部分追加到末尾
cur.next = l1 if l1 else l2
return res.next
解法二
遞歸□文溃基本思路與解法一相同镇饺，只是使用遞歸完成迭代
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2
if not l2: 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
