合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 
，每个节点的val满足 
要求：时间复杂度 )
[编程题]合并k个已排序的链表
// 思路1: 使用优先队列(实质与堆相差无几) priority_queue
/*
struct compare
{
bool operator()(const ListNode* l, const ListNode* r)
{
return l->val > r->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists)
{
priority_queue<ListNode *, vector<ListNode *>,compare> q; //compare
for(auto l:lists)
if(l) q.push(l);
if(q.empty()) return NULL;
ListNode fake(0);
ListNode *result = &fake;
while(!q.empty())
{
result->next = q.top();
q.pop();
result = result->next;
if(result->next)
q.push(result->next);
}
return fake.next;
}
*/
// 思路2：使用堆（默认最大堆，改成最小堆，链表依次加入最小堆弹出节点，加入该节点所在链表新节点，不断调整堆......STL中提供heap算法
static bool compareLess(ListNode* l1,ListNode* l2)
{
return l1->val > l2->val;
}
ListNode* mergeKLists(vector<ListNode*> &lists)
{
ListNode fake(0);
ListNode *cur = &fake;
vector<ListNode *> vec;
int listSize = lists.size();
for(int i=0;i<listSize;i++)
{
if(lists[i])
vec.push_back(lists[i]);
}
make_heap(vec.begin(),vec.end(),compareLess); // 建堆
while(vec.size())
{
cur->next = vec.front(); // 堆第一个节点first为最小值节点
pop_heap(vec.begin(),vec.end(),compareLess); // 它把first和last-1交换，然后重新生成一个堆
vec.pop_back(); // 容器弹出最后一个节点
cur = cur->next;
if(cur->next) // 添加弹出的最小值的节点所在链表节点 last-1位置
{
vec.push_back(cur->next);
push_heap(vec.begin(),vec.end(),compareLess); // first到last-1是一个有效堆，新加入元素重新生成堆
}
}
return fake.next;
}
// 思路3：分治算法，基于两个排序链表的合并，两两合并后继续合并，每一轮复杂度o(n),n为总节点个数，T(n) = 2T(n/2) + o(n),迭代次数为lg(k),因此复杂度为o(nlgk)
/*
ListNode* mergeTwoSortedLists(ListNode* L1,ListNode* L2)
{
if(L1== nullptr)
return L2;
if(L2==nullptr)
return L1;
if(L1->val <= L2->val)
{
L1->next = mergeTwoSortedLists(L1->next,L2);
return L1;
}
else
{
L2->next = mergeTwoSortedLists(L1,L2->next);
return L2;
}
}
ListNode* mergeKLists(vector<ListNode*> &lists)
{
if(lists.empty())
return nullptr;
while(lists.size()>1)
{
lists.push_back(mergeTwoSortedLists(lists[0],lists[1]));
lists.erase(lists.begin());
lists.erase(lists.begin());
}
return lists.front();
}
*/
发表于 2017-07-12 20:06:27
回复(12)
使用优先队列来求解问题，首先将链表数组的每个链表的头结点加入队列（因为链表是从小到大排序，所以没有必要一开始将所有的节点入队）
其他的直接看代码吧hhhhh，比较简单就不上备注了
import java.util.*;
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0)
return null;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), 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 tail = dummy;
for (ListNode node : lists)
if (node != null)
queue.add(node);
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
if (tail.next != null)
queue.add(tail.next);
}
return dummy.next;
}
}
编辑于 2018-05-31 21:36:22
回复(4)
直接排序value后生成新链表
ListNode *mergeKLists(vector<ListNode *> &lists) {
vector <int> vec;
if (lists.size() == 0)
return NULL;
for (int i = 0; i < lists.size(); ++i)
{
ListNode *p = lists[i];
while (p)
{
vec.push_back(p->val);
p = p->next;
}
}
sort(vec.begin(), vec.end());
if (vec.size() == 0)
return NULL;
ListNode *head = new ListNode(vec[0]);
ListNode *p = head;
for (int i = 1; i < vec.size(); ++i)
{
p->next = new ListNode(vec[i]);
p = p->next;
}
return head;
}
发表于 2017-09-29 17:55:07
回复(2)
import java.util.*;
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists.size() == 0) return null;
ListNode head = lists.get(0);
for (int i = 1; i < lists.size(); i ++ )
head = merge2Lists(head, lists.get(i));
return head;
}
public static ListNode merge2Lists(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0), p = dummy;
while (head1 != null && head2 != null) {
if(head1.val < head2.val) {
p.next = head1;
head1 = head1.next;
} else {
p.next = head2;
head2 = head2.next;
}
p = p.next;
}
p.next = (head1 == null) ? head2 : head1;
return dummy.next;
}
}
编辑于 2016-11-18 01:32:29
回复(3)
归并排序算法的时间复杂度是o(nlogn)
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists==null||lists.size()==0){
return null;
}
return mergeKList(lists,0,lists.size()-1);
}
public ListNode mergeKList(ArrayList<ListNode> lists,int lo,int hi){
if (hi<=lo) return lists.get(lo);
int mid=lo+(hi-lo)/2;
ListNode left = mergeKList(lists,lo,mid);
ListNode right = mergeKList(lists,mid+1,hi);
return merge(left,right);
}
public ListNode merge(ListNode left,ListNode right){
ListNode h = new ListNode(-1);
ListNode tmp=h;
while(left!=null&&right!=null){
if(left.val<right.val){
tmp.next=left;
//tmp=tmp.next;
left=left.next;
}else{
tmp.next=right;
// tmp=tmp.next;
right=right.next;
} tmp=tmp.next; }
if(left!=null){
tmp.next=left;
}
if(right!=null){
tmp.next=right;
}
return h.next;
}
}
发表于 2016-11-11 21:16:28
回复(5)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode *l1,ListNode *l2){
ListNode *cur1=l1;
ListNode *cur2=l2;
ListNode *newHead=new ListNode(0);
ListNode *cur=newHead;
while(cur1!=NULL &&cur2!=NULL){
if(cur1->val<cur2->val){
cur->next=cur1;
cur1=cur1->next;
}
else{
cur->next=cur2;
cur2=cur2->next;
}
cur=cur->next;
}
cur->next=(cur1==NULL)?cur2:cur1;
return newHead->next;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
int n=lists.size();
if(n==0) return NULL;
ListNode *res=lists[0];
for(int i=1;i<n;++i){
res=mergeTwoLists(res,lists[i]);
}
return res;
}
};
发表于 2016-09-17 10:53:35
回复(1)
解题思路很简单，使用优先队列，每次从队列中找到最小的数取出来，然后把该数的下一个结点添加到优先队列中（如果没有后继结点则不添加），直到队列为空，这个时候所有的链表都合并结束了。
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
//防御
if (lists.empty()) return NULL;
//初始化优先队列，空出第一个位置
a.resize(lists.size()+1, NULL);
n = 0;
for (int i=0; i<lists.size(); i++)
push(lists[i]);
//开始遍历所有的已排序链表，直到队列为空
ListNode *head = NULL, *tail = NULL;
while(n >= 1){
//出队
ListNode* pNode = pop();
//加到新的链表中
if(head == NULL){
head = new ListNode(pNode->val);
tail = head;
}
else
addNode(tail, pNode->val);
//加入出队的后继结点
push(pNode->next);
}
return head;
}
vector<ListNode*> a;
int n;
void addNode(ListNode* &p, int v){
ListNode* q = new ListNode(v);
p->next = q;
p = q;
}
void swap(int l, int m){
ListNode* temp = a[l];
a[l] = a[m];
a[m] = temp;
}
void swim(int k){
while(k>1 && a[k]->val < a[k/2]->val){//是子结点，并且小于父节点
swap(k, k/2);
k = k/2;
}
}
void sink(int k){
//只要有子结点
while (2*k <= n){
int j = 2*k;
//找到较小的子结点
if(j<n && a[j]->val > a[j+1]->val) j = j+1;
//如果父结点大于子结点，则交换
if(a[k]->val > a[j]->val) swap(k, j);
k = j;
}
}
void push(ListNode* p){
if (p == NULL) return;
//先在最后加入结点，再swim
a[++n] = p;
swim(n);
}
ListNode* pop(){
ListNode* retp = a[1];
swap(1, n--);
sink(1);
return retp;
}
};
发表于 2016-08-08 15:49:07
回复(0)
思路:两两合并思想
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists==null || lists.size()==0) {
return null;
}
while(lists.size()>1) {
ArrayList<ListNode> newList = new ArrayList<ListNode>();
for(int i=0;i+1<lists.size();i+=2) {
ListNode listnode = merge(lists.get(i),lists.get(i+1));
newList.add(listnode);
}
//如果是奇数,将最后一个链表添加到新的集合中
if(lists.size()%2!=0) {
newList.add(lists.get(lists.size()-1));
}
lists = newList;
}
return lists.get(0);
}
public ListNode merge(ListNode l1,ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
p.next = l1;
p = l1;
l1 = l1.next;
}else {
p.next = l2;
p = l2;
l2 = l2.next;
}
}
if(l1!=null) {
p.next = l1;
}
if(l2!=null) {
p.next = l2;
}
return dummy.next;
}
}
发表于 2016-03-15 14:58:20
回复(2)
递归：
#include <climits>
#include <list>
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto it = lists.begin(); it != lists.end();) {
if (*it == nullptr)
lists.erase(it);
else
++it;
}
if(lists.size()==0)
return nullptr;
int minIdx = -1, minVal = INT_MAX;
for (int i = 0; i < lists.size(); ++i)
if (lists[i]->val < minVal) {
minVal = lists[i]->val;
minIdx = i;
}
ListNode * p = lists[minIdx];
lists[minIdx] = lists[minIdx]->next;
if(lists[minIdx]==nullptr)
lists.erase(lists.begin()+minIdx);
p->next = mergeKLists(lists);
return p;
}
}; 优先级队列#include <queue>
struct Compare {
bool operator() (ListNode* p, ListNode* q) {
return p->val > q->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
for (int i = 0; i < lists.size(); ++i) {
if(lists[i])
pq.push(lists[i]);
}
ListNode node(-1),*p = &node;
while (!pq.empty()) {
ListNode * t = pq.top();
pq.pop();
p->next = t;
p = t;
if(t->next!=nullptr)
{
pq.push(t->next);
}
p->next = nullptr;
}
return node.next;
}
};
借助数组： #include <algorithm>
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// write code here
vector<int> vals;
for(auto & list : lists){
while(list){
vals.push_back(list->val);
list = list->next;
}
}
sort(vals.begin(), vals.end());
ListNode node(-1),*p = &node;
for(int i=0;i<vals.size();++i){
p->next = new ListNode(vals[i]);
p = p->next;
}
return node.next;
}
}; 归并： class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// write code here
ListNode head(0), *p = &head;
for (auto it = lists.begin(); it != lists.end();)
if (*it == nullptr)
lists.erase(it);
else
++it;
while (lists.size() != 0) {
int minVal = INT_MAX, minIdx = -1;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i]->val < minVal) {
minVal = lists[i]->val;
minIdx = i;
}
}
p->next = lists[minIdx];
p = lists[minIdx];
lists[minIdx] = lists[minIdx]->next;
p->next = nullptr;
if(lists[minIdx]==nullptr)
lists.erase(lists.begin()+minIdx);
}
return head.next;
}
};
发表于 2023-11-13 13:44:38
回复(0)
ListNode *mergeKLists(vector<ListNode *> &lists)
{
// 用红黑树的K-V结构来存储所有节点，K存的是节点的val，V存的是节点
// 存好之后就是有序的了
multimap<int, ListNode*> m1;
// 遍历取出所有链表
for (int i = 0; i < lists.size(); i++)
{
// 遍历当前链表的所有节点
ListNode* cur = lists[i];
while (cur)
{
// 将节点存入红黑树
m1.insert(make_pair(cur->val, cur));
cur = cur->next;
}
}
if (m1.size() == 0) // 树为空表明没有节点存入，直接返回空
{
return nullptr;
}
// 遍历红黑树，将所有节点连接起来
ListNode* head = m1.begin()->second;
ListNode* tail = nullptr;
for (auto& pair : m1)
{
if (tail)
{
tail->next = pair.second;
}
tail = pair.second;
}
return head;
}
发表于 2022-10-30 23:52:13
回复(1)
//分治
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
return DivideMerge(lists);
}
ListNode* DivideMerge(vector<ListNode*>& lists)
{
vector<ListNode*> list1;
vector<ListNode*> list2;
int count = lists.size();
for (int i = 0; i < count / 2; i++) {
list1.push_back(lists[i]);
}
for (int i = count / 2; i < count; i++) {
list2.push_back(lists[i]);
}
return MergeList(list1, list2);
}
ListNode* MergeList(vector<ListNode*>& list1, vector<ListNode*>& list2)
{
if(list1.size() == 1 && list2.size() == 1)
{
return Merge(list1[0], list2[0]);
}
else if(list1.size() == 1)
{
vector<ListNode*> temp;
temp.push_back(DivideMerge(list2));
return MergeList(list1, temp);
}
else if(list2.size() == 1)
{
vector<ListNode*> temp;
temp.push_back(DivideMerge(list1));
return MergeList(temp, list2);
}
else
{
vector<ListNode*> temp1;
vector<ListNode*> temp2;
temp1.push_back(DivideMerge(list1));
temp2.push_back(DivideMerge(list2));
return MergeList(temp1, temp2);
}
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if (pHead1 == NULL) return pHead2;
if (pHead2 == NULL) return pHead1;
ListNode* res;
ListNode* temp;
if (pHead1->val < pHead2->val) {
temp = pHead1;
pHead1 = pHead1->next;
} else {
temp = pHead2;
pHead2 = pHead2->next;
}
res = temp;
while (pHead1 != NULL || pHead2 != NULL) {
if (pHead1 == NULL) {
temp->next = pHead2;
break;
}
if (pHead2 == NULL) {
temp->next = pHead1;
break;
}
if (pHead1->val < pHead2->val) {
temp->next = pHead1;
temp = pHead1;
pHead1 = pHead1->next;
} else {
temp->next = pHead2;
temp = pHead2;
pHead2 = pHead2->next;
}
}
return res;
}
};
发表于 2022-04-16 11:31:12
回复(0)
主要有两个比较好的方法，一个是堆，一个是分治。
js写这个题。如果使用堆(优先队列)的话，难点是需要自己实现堆的数据结构。c或java好像都有内置已经写好的优先队列数据解构。
js利用数组实现堆需要注意的是：
- push添加元素的时候，向数组尾部添加元素，如果向其他位置添加元素的话(比如数组开头)，会整个打乱堆，需要重新初始化堆。如果向尾部添加元素，只需要重新初始化树的一半就行。
- 如果要删除开头元素。将开头元素后尾部元素交换后在删除尾部元素。因为直接删除打乱了整个堆的解构，需要重新初始化，而删除尾部元素不会打乱堆，可以只初始化一边。
function mergeKLists( lists ) {
if (lists.length <= 1) return lists[0] || null;
let heap = new minHeap(), head = {next: null}, p = head;
for (let i=0; i<lists.length; ++i) {
if (lists[i]) {
heap.push(lists[i]);
}
}
while(heap.heap.length) {
p.next = heap.pop();
p = p.next;
if (p.next) {
heap.push(p.next);
}
}
return head.next;
}
class minHeap {
constructor() {
this.heap = [];
}
push(node) {
this.heap.push(node);
let i = this.heap.length-1, dad = Math.floor((i-1)/2);
while(dad >= 0) {
this.minHeap(dad, i);
dad = Math.floor((dad-1)/2);
}
}
pop() {
const i=0, j=this.heap.length-1;
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
const res = this.heap.splice(j, 1);
this.minHeap(0, j-1);
return res[0];
}
minHeap(l, r) {
let dad = l, son = dad*2+1;
if (son > r) return;
if (son + 1 <= r && this.heap[son+1].val < this.heap[son].val) {
++son;
}
if (this.heap[son].val < this.heap[dad].val) {
[this.heap[dad], this.heap[son]] = [this.heap[son], this.heap[dad]]
this.minHeap(son, r);
}
}
}分治法：
function mergeKLists( lists ) {
if (lists.length <= 1) return lists[0] || null;
return merge(lists, 0, lists.length-1);
}
function merge(lists, l, r) {
if (l > r) return null;
if (l === r) return lists[l];
const mid = Math.floor((l+r)/2);
return mergeTwoList(merge(lists, l, mid), merge(lists, mid+1, r));
}
function mergeTwoList (list1, list2) {
if (!list1 || !list2) return list1 || list2;
let p1 = list1, p2 = list2, head = {next: null}, p = head;
while(p1 && p2) {
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
p.next = p1 || p2;
return head.next;
}
发表于 2021-11-26 15:21:15
回复(0)
Python Solution:
def __init__(self, x): self.val = x self.next = None # # # @param lists ListNode类一维数组 # @return ListNode类 # class Solution: def mergeKLists(self , lists ): # write code here newHead=ListNode(0) cur=newHead lists=[x for x in lists if x] while lists: lists=sorted(lists,key=lambda x:x.val) cur.next=lists[0] cur=cur.next lists[0]=lists[0].next lists=[x for x in lists if x] return newHead.next
发表于 2020-09-06 13:05:14
回复(0)
import java.util.ArrayList;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0){
return null;
}
if (lists.size() == 1){
return lists.get(0);
}
int begin = 0;
int end = lists.size() - 1;
while (end>0){
begin = 0;
while (begin<end){
lists.set(begin,mergeTwoLists(lists.get(begin),lists.get(end)));
begin++;
end--;
}
}
return lists.get(0);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode mergeNode = null;
if (l1.val > l2.val) {
mergeNode = l2;
mergeNode.next = mergeTwoLists(l1, l2.next);
} else {
mergeNode = l1;
mergeNode.next = mergeTwoLists(l1.next, l2);
}
return mergeNode;
}
}
发表于 2018-08-09 23:07:59
回复(0)
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode L(0);
ListNode *p = &L;
vector<ListNode *> v;
int n = lists.size();
for(int i=0;i<n;i++)
if(lists[i] != NULL)
v.push_back(lists[i]);
make_heap(v.begin(),v.end(),cmp);
while(v.size())
{
p->next = v.front();
pop_heap(v.begin(),v.end(),cmp);
v.pop_back();
p = p->next;
if(p->next)
{
v.push_back(p->next);
push_heap(v.begin(),v.end(),cmp);
}
}
return L.next;
}
static bool cmp(ListNode *L1,ListNode *L2)
{
return L1->val > L2->val;
}
};
发表于 2017-09-10 01:32:53
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.size()==0)
return nullptr;
ListNode *p=lists[0];
for(int i=1;i<lists.size();i++)
p=mergeTwoLists(p,lists[i]);
return p;
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode dummy(-1);
ListNode *p=&dummy;
for(;l1!=NULL&&l2!=NULL;p=p->next){
if(l1->val>l2->val){
p->next=l2;
l2=l2->next;
}
else{
p->next=l1;
l1=l1->next;
}
}
p->next=l1!=NULL?l1:l2;
return dummy.next;
}
};
发表于 2017-07-24 10:58:32
回复(3)
//cpp/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode*>& lists) { // write code here int b = 0; int num = lists.size(); int* a = new int[2005]; for(int i = 0;i<2005;i++){ a[i] = 0; } ListNode* temp = nullptr; for(int i = 0;i<num;i++){ temp = lists[i]; while(temp){ b = temp->val; a[b+1000]++; temp = temp->next; } } ListNode* p = nullptr; ListNode* head = nullptr; bool flag = false; for(int i = 0;i<=2000;i++){ if(a[i]==0){ continue; }else{ while(a[i]>0){ temp = new ListNode(i-1000); if(flag == false){ head = temp; flag = true; p = temp; a[i]--; }else{ p->next = temp; p = temp; a[i]--; } } } } return head; } };
发表于 2023-12-09 13:47:51
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类ArrayList
* @return ListNode类
*/
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
if(lists.size()==0||lists == null) return null;
ListNode head = lists.get(0);
for(int i = 1;i<lists.size();i++) {
head = getNode(head,lists.get(i));
}
return head;
}
public ListNode getNode(ListNode pHead1,ListNode pHead2) {
if(pHead1==null) return pHead2;
if(pHead2==null) return pHead1;
ListNode sentinel = new ListNode(-1);
ListNode cur = sentinel;
while(pHead1!=null&&pHead2!=null) {
if(pHead1.val > pHead2.val) {
cur.next = pHead2;
pHead2 = pHead2.next;
}else{
cur.next = pHead1;
pHead1 = pHead1.next;
}
cur = cur.next;
}
if(pHead1==null) cur.next = pHead2;
else cur.next = pHead1;
return sentinel.next;
}
}
发表于 2023-11-03 18:01:00
回复(0)
class Solution {
public:
priority_queue<int> res;
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return NULL;
for(auto p : lists)
while(p){
res.push(p -> val);
p = p -> next;
}
ListNode * head = new ListNode(-1);
while(res.size()){
ListNode * q = new ListNode(res.top());
res.pop();
q -> next = head -> next;
head -> next = q;
}
return head -> next;
}
};
发表于 2023-08-12 21:52:23
回复(0)
HEAPQ python实现
import heapq
class Solution:
def mergeKLists(self , lists: List[ListNode]) -> ListNode:
# write code here
heap = []
count = 0
for node in lists:
if node:
heap.append((node.val,count,node))
count+=1
heapq.heapify(heap)
retval = ListNode(-1)
cur = retval
while heap:
cur.next = heapq.heappop(heap)[2]
cur = cur.next
if cur.next:
heapq.heappush(heap,(cur.next.val,count,cur.next))
count+=1
return retval.next
发表于 2023-06-10 22:55:12
回复(0)
问题信息
难度：
416条回答
1469收藏
28505浏览
通过挑战的用户
查看代码-
2023-02-17 16:17:54 -
2022-12-25 13:07:31
-
2022-11-25 17:06:16 -
2022-09-30 21:52:48
-
2022-09-28 22:26:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
