加载中...
23-合并K个升序链表(Merge k Sorted Lists)
发表于:2021-12-03 | 分类: 困难
字数统计: 1k | 阅读时长: 5分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/merge-k-sorted-lists

英文原文

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won't exceed 10^4.

中文题目

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

 

示例 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

通过代码

高赞题解

思路:

思路 1:

优先级队列

时间复杂度:$O(n*log(k))$,n 是所有链表中元素的总和,k 是链表个数。

思路 2:

分而治之

链表两两合并

代码:

思路 1:

[]
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import heapq dummy = ListNode(0) p = dummy head = [] for i in range(len(lists)): if lists[i] : heapq.heappush(head, (lists[i].val, i)) lists[i] = lists[i].next while head: val, idx = heapq.heappop(head) p.next = ListNode(val) p = p.next if lists[idx]: heapq.heappush(head, (lists[idx].val, idx)) lists[idx] = lists[idx].next return dummy.next
[]
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { if (o1.val < o2.val) return -1; else if (o1.val == o2.val) return 0; else return 1; } }); ListNode dummy = new ListNode(0); ListNode p = dummy; for (ListNode node : lists) { if (node != null) queue.add(node); } while (!queue.isEmpty()) { p.next = queue.poll(); p = p.next; if (p.next != null) queue.add(p.next); } return dummy.next; } }

思路 2:

分而治之

[]
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists:return n = len(lists) return self.merge(lists, 0, n-1) def merge(self,lists, left, right): if left == right: return lists[left] mid = left + (right - left) // 2 l1 = self.merge(lists, left, mid) l2 = self.merge(lists, mid+1, right) return self.mergeTwoLists(l1, l2) def mergeTwoLists(self,l1, l2): if not l1:return l2 if not l2:return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
[]
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int left, int right) { if (left == right) return lists[left]; int mid = left + (right - left) / 2; ListNode l1 = merge(lists, left, mid); ListNode l2 = merge(lists, mid + 1, right); return mergeTwoLists(l1, l2); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1,l2.next); return l2; } } }

统计信息

通过次数 提交次数 AC比率
354917 632291 56.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
合并两个有序链表 简单
丑数 II 中等
上一篇:
22-括号生成(Generate Parentheses)
下一篇:
24-两两交换链表中的节点(Swap Nodes in Pairs)
本文目录
本文目录