# 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]:
# 保存结果的链表
result = ListNode()
# 移动的指针
cur = result
cur1 = list1
cur2 = list2
# 判断待比较的链表是否一个为空
if cur1 == None:
return list2
if cur2 == None:
return list1
# 若两个链表都不为空
while True:
# 当两个当前节点都不为空,作比较
if cur1.val < cur2.val:
cur.val = cur1.val
cur1 = cur1.next
else:
cur.val = cur2.val
cur2 = cur2.next
# 如果有一个为空,不用创建新结点,直接指向不为空的结点
if cur1 == None:
cur.next = cur2
break
if cur2 == None:
cur.next = cur1
break
# 创建新结点
cur.next = ListNode()
cur = cur.next
return result
题目:合并K个有序链表
两两合并转化为上面的题目
使用遍历,时间会超时。
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
n = len(lists)
res = lists[0]
# 将lists[0]作为最终合并的链表,然后将list[0]和lists[1]合并成lists[0-1]
# 再将lists[0-1]和lists[2]合并,如此反复最终lists[0]就是最终结果
for i in range(1,n):
res = self.mergeTwoLists(res,lists[i])
return res
使用堆排序的思想:分而治之的算法,即先使每个子序列有序,再使子序列段间有序,时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
if n == 0: return None
if n == 1: return lists[0]
mid = n // 2
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)