【Leetcode】链表-21,23
  KRe60ogUm4le 18天前 77 0

单链表---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. 堆(二叉树)

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 18天前 0

暂无评论

推荐阅读
KRe60ogUm4le
最新推荐 更多

2024-05-31