| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
困难 |
|
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
我们可以创建一个小根堆来
时间复杂度
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)
pq = [head for head in lists if head]
heapify(pq)
dummy = cur = ListNode()
while pq:
node = heappop(pq)
if node.next:
heappush(pq, node.next)
cur.next = node
cur = cur.next
return dummy.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 {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) {
if (head != null) {
pq.offer(head);
}
}
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
if (node.next != null) {
pq.offer(node.next);
}
cur.next = node;
cur = cur.next;
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
for (auto head : lists) {
if (head) {
pq.push(head);
}
}
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
if (node->next) {
pq.push(node->next);
}
cur->next = node;
cur = cur->next;
}
return dummy->next;
}
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
pq := hp{}
for _, head := range lists {
if head != nil {
pq = append(pq, head)
}
}
heap.Init(&pq)
dummy := &ListNode{}
cur := dummy
for len(pq) > 0 {
cur.Next = heap.Pop(&pq).(*ListNode)
cur = cur.Next
if cur.Next != nil {
heap.Push(&pq, cur.Next)
}
}
return dummy.Next
}
type hp []*ListNode
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const pq = new MinPriorityQueue({ priority: (node: ListNode) => node.val });
for (const head of lists) {
if (head) {
pq.enqueue(head);
}
}
const dummy: ListNode = new ListNode();
let cur: ListNode = dummy;
while (!pq.isEmpty()) {
const node = pq.dequeue().element;
cur.next = node;
cur = cur.next;
if (node.next) {
pq.enqueue(node.next);
}
}
return dummy.next;
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::cmp::Ordering;
use std::collections::BinaryHeap;
impl PartialOrd for ListNode {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ListNode {
fn cmp(&self, other: &Self) -> Ordering {
self.val.cmp(&other.val).reverse()
}
}
impl Solution {
pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
let mut pq = lists
.into_iter()
.filter_map(|head| head)
.collect::<BinaryHeap<_>>();
let mut head = None;
let mut cur = &mut head;
while let Some(node) = pq.pop() {
cur = &mut cur.insert(Box::new(ListNode::new(node.val))).next;
if let Some(next) = node.next {
pq.push(next);
}
}
head
}
}/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
const pq = new MinPriorityQueue({ priority: node => node.val });
for (const head of lists) {
if (head) {
pq.enqueue(head);
}
}
const dummy = new ListNode();
let cur = dummy;
while (!pq.isEmpty()) {
const node = pq.dequeue().element;
cur.next = node;
cur = cur.next;
if (node.next) {
pq.enqueue(node.next);
}
}
return dummy.next;
};/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
PriorityQueue<ListNode, int> pq = new PriorityQueue<ListNode, int>();
foreach (var head in lists) {
if (head != null) {
pq.Enqueue(head, head.val);
}
}
var dummy = new ListNode();
var cur = dummy;
while (pq.Count > 0) {
var node = pq.Dequeue();
cur.next = node;
cur = cur.next;
if (node.next != null) {
pq.Enqueue(node.next, node.next.val);
}
}
return dummy.next;
}
}# Definition for singly-linked list.
class ListNode {
public $val;
public $next;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
/**
* @param ListNode[] $lists
* @return ListNode
*/
function mergeKLists($lists) {
$numLists = count($lists);
if ($numLists === 0) {
return null;
}
while ($numLists > 1) {
$mid = intval($numLists / 2);
for ($i = 0; $i < $mid; $i++) {
$lists[$i] = $this->mergeTwoLists($lists[$i], $lists[$numLists - $i - 1]);
}
$numLists = intval(($numLists + 1) / 2);
}
return $lists[0];
}
function mergeTwoLists($list1, $list2) {
$dummy = new ListNode(0);
$current = $dummy;
while ($list1 != null && $list2 != null) {
if ($list1->val <= $list2->val) {
$current->next = $list1;
$list1 = $list1->next;
} else {
$current->next = $list2;
$list2 = $list2->next;
}
$current = $current->next;
}
if ($list1 != null) {
$current->next = $list1;
} elseif ($list2 != null) {
$current->next = $list2;
}
return $dummy->next;
}
}