Open azl397985856 opened 1 year ago
归并排序
#先合并两个,两两合并最后再合到一起
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
# basic cases
if n == 0: return None
if n == 1: return lists[0]
if n == 2: return self.mergeTwoLists(lists[0], lists[1])
# divide and conqure if not basic cases
mid = n // 2
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
c1, c2, c3 = l1, l2, res
while c1 or c2:
if c1 and c2:
if c1.val < c2.val:
c3.next = ListNode(c1.val)
c1 = c1.next
else:
c3.next = ListNode(c2.val)
c2 = c2.next
c3 = c3.next
elif c1:
c3.next = c1
break
else:
c3.next = c2
break
return res.next
复杂度分析
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
class Status implements Comparable<Status>{
int val;
ListNode ptr;
Status(int val, ListNode ptr){
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2){
return this.val - status2.val;
}
}
PriorityQueue<Status> queue = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {
for(ListNode node: lists){
if(node != null){
queue.offer(new Status(node.val, node));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while(!queue.isEmpty()){
Status f = queue.poll();
tail.next = f.ptr;
tail = tail.next;
if(f.ptr.next != null){
queue.offer(new Status(f.ptr.next.val, f.ptr.next));
}
}
return head.next;
}
}
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
if l1:
current.next = l1
if l2:
current.next = l2
return dummy.next
def mergeSortLists(lists, left, right):
if left == right:
return lists[left]
mid = left + (right - left) // 2
left_list = mergeSortLists(lists, left, mid)
right_list = mergeSortLists(lists, mid + 1, right)
return mergeTwoLists(left_list, right_list)
if not lists:
return None
return mergeSortLists(lists, 0, len(lists) - 1)
23.合并 K 个排序链表
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/merge-k-sorted-lists/
前置知识
题目描述
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入: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 示例 2:
输入:lists = [] 输出:[] 示例 3:
输入:lists = [[]] 输出:[]
提示:
k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4