LeetCode链接
迭代 时间复杂度 O(n + m)# 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]:
dummyNode = ListNode()
pre = dummyNode
while list1 and list2:
if list1.val <= list2.val:
pre.next = list1
list1 = list1.next
else:
pre.next = list2
list2 = list2.next
pre = pre.next
# 此处至多还剩一个链表有内容 接上即可
pre.next = list1 if list1 else list2
return dummyNode.next
递归 时间复杂度 O(n + m)
# 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 not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
