单链表---21
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 两个链表的节点数目范围是
[0, 50]-
-100 <= Node.val <= 100-
l1 和 l2 均按 非递减顺序 排列
输入输出：
输入：l1 = [], l2 = [] 输出：[]
解题思路：
python数据结构之链表
算法实现：
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
ans = ListNode(0)
p = ans
while l1 and l2:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
if l1:
p.next = l1
elif l2:
p.next = l2
return ans.next
优先队列---23
题目：
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入输出：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
解题思路：
方法一：
方法二：
方法三：
方法四：
算法实现：
# 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
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
l = len(lists)
if l == 0:
return None
elif l == 1:
return lists[0]
else:
p = self.mergeTwoLists(lists[0],lists[1])
for i in range(2,l):
p = self.mergeTwoLists(p,lists[i])
return p
方法三：分而治之
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def merge(self, node_a, node_b):
dummy = ListNode(None)
cursor_a, cursor_b, cursor_res = node_a, node_b, dummy
while cursor_a and cursor_b: # 对两个节点的 val 进行判断，直到一方的 next 为空
if cursor_a.val <= cursor_b.val:
cursor_res.next = ListNode(cursor_a.val)
cursor_a = cursor_a.next
else:
cursor_res.next = ListNode(cursor_b.val)
cursor_b = cursor_b.next
cursor_res = cursor_res.next
# 有一方的next的为空，就没有比较的必要了，直接把不空的一边加入到结果的 next 上
if cursor_a:
cursor_res.next = cursor_a
if cursor_b:
cursor_res.next = cursor_b
return dummy.next
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
length = len(lists)
# 边界情况
if length == 0:
return None
if length == 1:
return lists[0]
# 分治
mid = length // 2
return self.merge(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:length]))
出现问题：
1. 优先队列：
2. 堆（二叉树）