合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 
，每个节点的val满足 
要求：时间复杂度 )
[编程题]合并k个已排序的链表
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
if (lists == null || lists.isEmpty()) return null;
Iterator<ListNode> it = lists.iterator();
ListNode res = it.next();
while (it.hasNext()) res = merge(res, it.next());
return res;
}
private ListNode merge(ListNode a, ListNode b) {
if (a == null) return b;
if (b == null) return a;
if(a.val <= b.val) {
a.next = merge(a.next, b);
return a;
} else {
b.next = merge(b.next, a);
return b;
}
}
发表于 2024-04-15 10:45:12
回复(0)
多链表合并
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类ArrayList
* @return ListNode类
*/
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
ListNode head=new ListNode(0), cur=head, min=head;
int minIdx=0;
while(true){
min=null;
for(int i=0;i<lists.size();++i){
if(lists.get(i)!=null){
if(min==null){
min=lists.get(i);
minIdx=i;
}else if(min.val>lists.get(i).val){
min=lists.get(i);
minIdx=i;
}
}
}
if(min==null)
break;
cur.next=min;
cur=min;
lists.set(minIdx, min.next);
}
return head.next;
}
}
编辑于 2024-02-19 19:21:51
回复(0)
public ListNode mergeKLists(ArrayList<ListNode> lists) { PriorityQueue<ListNode> list = new PriorityQueue<>(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 1; } else { return 0; } } }); // write code here ListNode result = null; //把所有node放到优先级队列中，自动排序，最后一个node的next设置为null即可 for (ListNode listNode : lists) { if (null == listNode) { continue; } while (null != listNode) { list.add(listNode); listNode = listNode.next; } } ListNode cur = null; while (!list.isEmpty()) { if (null == result) { result = cur = list.poll(); } else { cur.next = list.poll(); cur = cur.next; } } if (null != cur) { cur.next = null; } return result; }
发表于 2024-01-21 16:30:03
回复(0)
public ListNode mergeKLists (ArrayList<ListNode> lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((x1, x2) -> x1.val - x2.val);
// pq.addAll(lists.stream().filter(x -> x != null).toList());
for (ListNode head : lists) {
if (head != null) {
pq.add(head);
}
}
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (pq.size() > 0) {
ListNode top = pq.poll();
p.next = top;
top = top.next;
p = p.next;
if (top != null) {
pq.add(top);
}
}
return dummy.next;
}
发表于 2023-11-08 22:24: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)
public ListNode mergeKLists (ArrayList<ListNode> lists) {
ArrayList<Integer> arr = new ArrayList<>();
ListNode ret = new ListNode();
ListNode temp;
for (ListNode listNode : lists) {
temp = listNode;
while (temp != null) {
arr.add(temp.val);
temp = temp.next;
}
}
arr.sort(Integer::compareTo);
temp = ret;
for (int i = 0; i < arr.size(); i++) {
temp.val = arr.get(i);
if (temp.next == null && i != arr.size() - 1) {
temp.next = new ListNode();
temp = temp.next;
}
}
if(ret.val==0&&ret.next==null){
return null;
}
return ret;
}
}
发表于 2023-10-09 10:37:34
回复(1)
public class Solution {
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
return mergeKList(lists, 0, lists.size() - 1);
}
// 2、递归+分治 O(logn * n)
public ListNode mergeKList(ArrayList<ListNode> lists, int left,int right){
// 递归终点
if(left == right){
return lists.get(left);
}
if(left > right){
return null;
}
// 取中间值
int mid = left + ((right - left) >> 1);
// 递归调用到最基础的俩俩合并
// 分治左右，实现list中的节点元素可以呈树形俩俩合并，实现logn，配合俩俩合并，总时间复杂度nlogn
return merge(mergeKList(lists,left,mid),mergeKList(lists,mid+1,right));
}
// 1、（基础）俩个链表合并 O(n)
public ListNode merge(ListNode l1, ListNode l2){
if(l1 == null || l2 == null){
return l1 == null ? l2 : l1;
}
// 返回节点
ListNode dummy = new ListNode(-1);
// 操作节点
ListNode cur = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
// 补齐剩下未合并完的链
cur.next = (l1 == null ? l2 : l1);
return dummy.next;
}
}
发表于 2023-09-26 01:48:28
回复(0)
public ListNode mergeKLists (ArrayList<ListNode> lists) {
if (lists.size() == 0) {
return null;
}
Iterator iterator = lists.iterator();
while(iterator.hasNext()) {
if (iterator.next() == null) {
iterator.remove();
}
}
ListNode dummy = new ListNode(-1), tail = dummy;
while (!(lists.size() == 0)) {
int minIdx = 0;
for (int i = 1; i < lists.size(); i++) {
if (lists.get(minIdx).val > lists.get(i).val) {
minIdx = i;
}
}
tail.next = lists.get(minIdx);
if (lists.get(minIdx).next == null) {
lists.remove(minIdx);
} else {
lists.set(minIdx, lists.get(minIdx).next);
}
tail = tail.next;
tail.next = null;
}
return dummy.next;
}
发表于 2023-09-13 16:44:32
回复(0)
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
ListNode res = new ListNode(-1001);
ListNode cur = res;
while(true){
ListNode temp = new ListNode(1001);
int flag = -1;
for(int i=0; i<lists.size(); i++){
if(lists.get(i) != null && lists.get(i).val < temp.val){
temp = lists.get(i);
flag = i;
}
}
if(flag == -1){
return res.next;
}
if(lists.get(flag).next != null){
lists.add(lists.get(flag).next);
}
cur.next = lists.get(flag);
cur = cur.next;
cur.next = null;
lists.remove(flag);
}
}
发表于 2023-08-15 17:07:04
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类ArrayList
* @return ListNode类
*/
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
return mergeList(lists, 0, lists.size() - 1);
}
// 二分递归
public ListNode mergeList(ArrayList<ListNode> lists, int l, int r) {
if (l == r) {
return lists.get(l);
}
if (l > r) {
return null;
}
int mid = (l + r ) / 2;
return merge(mergeList(lists,l, mid), mergeList(lists, mid + 1, r));
}
// 合并两个链表
public ListNode merge(ListNode left, ListNode right) {
ListNode res = new ListNode(0);
ListNode temp = res;
while (left != null || right != null) {
if (left != null && right != null) {
if (left.val <= right.val) {
temp.next = left;
temp = temp.next;
left = left.next;
} else {
temp.next = right;
temp = temp.next;
right = right.next;
}
} else if (left != null) {
temp.next = left;
temp = temp.next;
left = left.next;
} else {
temp.next = right;
temp = temp.next;
right = right.next;
}
}
return res.next;
}
}
发表于 2023-08-14 16:21:54
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类ArrayList
* @return ListNode类
*/
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
for(ListNode list : lists) {
while(list != null) {
heap.add(list);
list = list.next;
}
}
ListNode head = heap.poll();
ListNode tail = head;
while(!heap.isEmpty()) {
ListNode cur = heap.poll();
tail.next = cur;
tail = cur;
if(heap.isEmpty()) {
tail.next = null;
}
}
return head;
}
class ListNodeComparator implements Comparator<ListNode> {
@Override
public int compare(ListNode o1,ListNode o2) {
return o1.val - o2.val;
}
}
}
发表于 2023-08-12 21:35:41
回复(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.isEmpty()) {
return null;
}
int size = lists.size();
int mod = size%2;
ArrayList<ListNode> newList = new ArrayList<>();
if (mod != 0) {
newList.add(lists.get(size/2));
}
for (int i = 0; i < size/2; i++) {
newList.add(merge(lists.get(i), lists.get(size - (i+1))));
}
if (1 == newList.size()) {
return newList.get(0);
}
return mergeKLists(newList);
}
public ListNode merge(ListNode list1, ListNode list2) {
if (null == list1) {
return list2;
}
if (null == list2) {
return list1;
}
if (list1.val >= list2.val) {
list2.next = merge(list1, list2.next);
return list2;
} else {
list1.next = merge(list1.next, list2);
return list1;
}
}
}
发表于 2023-03-07 23:14:37
回复(0)
递归
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
ListNode root = null;
for(int i=0; i<lists.size(); i++){
if(lists.get(i)==null) {
lists.remove(i);
i--;
}
}
if(lists.size()==0)
return root;
int min = lists.get(0).val;
int indexMin = 0;
for(int i=0; i<lists.size(); i++){
if(min>lists.get(i).val){
indexMin = i;
min = lists.get(i).val;
}
}
root= lists.get(indexMin);
lists.set(indexMin, lists.get(indexMin).next);
root.next = mergeKLists(lists);
return root;
}
}
发表于 2023-02-22 11:02:42
回复(0)
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);
}
ListNode left = mergeKLists(new ArrayList(lists.subList(0, lists.size() / 2)));
ListNode right = mergeKLists(new ArrayList(lists.subList(lists.size() / 2,
lists.size())));
ListNode res = new ListNode(-1);
ListNode h = res;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
if (left != null) {
h.next = left;
}
if (right != null) {
h.next = right;
}
return res.next;
}
}
发表于 2023-02-16 21:45:34
回复(0)
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
List<Integer> list = new ArrayList<>();
for (ListNode data: lists) {
while (data != null) {
list.add(data.val);
data = data.next;
}
}
Collections.sort(list);
ListNode pre = new ListNode(0);
ListNode cur = pre;
for (int data: list) {
ListNode listNode = new ListNode(data);
cur.next = listNode;
cur = listNode;
}
return pre.next;
}
}
发表于 2023-01-17 14:15:52
回复(0)
邪道写法，遍历->把值保存进数组->sort排序->新建链表输出
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < lists.size(); i++) {
ListNode inList = lists.get(i);
while (inList != null) {
arr.add(inList.val);
inList = inList.next;
}
}
Object[] aa = arr.toArray();
Arrays.sort(aa);
ListNode result = new ListNode(1);
ListNode buff = result;
System.out.print(aa);
for(int i = 0;i<arr.size();i++){
ListNode inResult = new ListNode((int)aa[i]);
result.next = inResult;
result = result.next;
}
result.next = null;
return buff.next;
}
}
发表于 2023-01-03 22:38:07
回复(0)
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
// 加表头
ListNode head = new ListNode(-1);
ListNode cur = head;
while (true) {
// 是否全部都走到尽头 第一个不是空的序列赋值给min
int flag = -1;
// 哪个序列是最小的序列
int which = 0;
int min = 1000;
// for(ListNode node : lists){
for(int i = 0;i<lists.size();i++){
// 判断是不是全部都为空 第一个不是空的序列赋值给min
if(lists.get(i) != null && flag == -1){
flag = 1;
min = lists.get(i).val;
}
if(lists.get(i) != null && lists.get(i).val <= min){
min = lists.get(i).val;
cur.next = lists.get(i);
which = i;
}
}
if (flag == -1) break;
cur = cur.next;
// 列表中的某一个序列 往后走一步
lists.set(which,lists.get(which).next);
}
//去掉表头
return head.next;
}
}
发表于 2022-12-10 12:13:09
回复(0)
问题信息
难度：
87条回答
1291收藏
26662浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
