23. Merge k Sorted Lists
Problem’s Link
—————————————————————————-
Mean:
将k个有序链表合并为一个有序链表.
analyse:
方法一：本着不重复发明轮子的原则，使用两两合并，就可以利用前面已经做过的Merge two Sorted Lists.
方法二：抖机灵.将所有结点的val都push_back在一个vector容器中，排序后又重新构造链表.
Time complexity: O(N)
view code
方法一：
*
mergeKLists(
vector
<
ListNode
*>
&
lists)
{
if(
lists
.
empty
()){
return
nullptr;
}
while(
lists
.
size()
>
1
){
lists
.
push_back(
mergeTwoLists(
lists
[
0
],
lists
[
1
]));
lists
.
erase(
lists
.
begin());
lists
.
erase(
lists
.
begin());
}
return
lists
.
front();
}
ListNode
*
mergeTwoLists(
ListNode
*
l1
,
ListNode
*
l2)
{
if(
l1
==
nullptr
){
return
l2;
}
if(
l2
==
nullptr
){
return
l1;
}
if(
l1
->
val
<=
l2
->
val
){
l1
->
next
=
mergeTwoLists(
l1
->
next
,
l2);
return
l1;
}
else
{
l2
->
next
=
mergeTwoLists(
l1
,
l2
->
next);
return
l2;
}
}
方法二：
* —————————————————————–
* Copyright (c) 2016 crazyacking.All rights reserved.
* —————————————————————–
* Author: crazyacking
* Date : 2016-02-18-09.02
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using
namespace
std;
typedef
long
long(
LL);
typedef
unsigned
long
long(
ULL);
const
double
eps(
1e-8);
// 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)
{
vector
<
int
>
nodeVal;
for(
auto
ptr:
lists)
{
while(
ptr)
{
nodeVal
.
push_back(
ptr
->
val);
ptr
=
ptr
->
next;
}
}
if(
nodeVal
.
size()
<=
0)
{
return
nullptr;
}
sort(
nodeVal
.
begin
(),
nodeVal
.
end());
bool
isFirst
=
1;
ListNode
*
res
=
nullptr
,
*
head
=
nullptr;
for(
auto
p:
nodeVal)
{
if(
isFirst)
{
isFirst
=
0;
head
=
new
ListNode(p);
res
=
head;
}
else
{
head
->
next
=
new
ListNode(p);
head
=
head
->
next;
}
}
return
res;
}
};
ListNode
*
getList(
vector
<
int
>&
arr)
{
bool
isFirst
=
1;
ListNode
*
res
=
nullptr
,
*
head
=
nullptr;
for(
auto
p:
arr)
{
if(
isFirst)
{
isFirst
=
0;
head
=
new
ListNode(p);
res
=
head;
}
else
{
head
->
next
=
new
ListNode(p);
head
=
head
->
next;
}
}
return
res;
}
int
main()
{
Solution
solution;
int n;
while(
cin
>>n)
{
vector
<
ListNode
*>
listVe;
while(n
—)
{
int
num;
cin
>>
num;
vector
<
int
>
ve;
for(
int
i
=
0;
i
<
num;
++
i)
{
int
tmp;
cin
>>
tmp;
ve
.
push_back(
tmp);
}
listVe
.
push_back(
getList(
ve));
}
ListNode
*
head
=
solution
.
mergeKLists(
listVe);
while(
head)
{
cout
<<
head
->
val
<<
” “;
head
=
head
->
next;
}
cout
<<
“End.”
<<
endl;
}
return
0;
}
/*
*/
转载于:https://www.cnblogs.com/crazyacking/p/5200073.html
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/109148.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
