21. 合并两个有序链表
来源: 21. 合并两个有序链表
1. 解题思路
递归或者非递归
2. 代码
2.1 递归
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
2.2 非递归
class Solution(object):
def mergeTwoLists(self, l1, l2):
head = ListNode(0)
front = head
while l1 or l2:
if not l1:
front.next = l2
return head.next
elif not l2:
front.next = l1
return head.next
else:
if l1.val>=l2.val:
front.next = l2
l2 = l2.next
else:
front.next = l1
l1 = l1.next
front = front.next
return head.next
