【每日一题】【小根堆&边出队边入队后续节点&注意判空】23. 合并K个升序链表-211128/220213
2024-10-20 16:25:48
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
答案1（参数是数组）：
/**
* 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) {
if(lists.length == 0) {
return null;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
//后大前小
PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
for(ListNode list : lists) {
if(list == null) {
continue;
}
pq.add(list);
}
while(!pq.isEmpty()) {
ListNode next = pq.poll();
cur.next = next;
cur = cur.next;
if(next.next != null) {
pq.add(next.next);
}
}
return dummy.next;
}
}
答案2：（参数是ArrayList）
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) {
ListNode res = new ListNode(0);
ListNode cur = res;
PriorityQueue<ListNode> queue =
new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
for(ListNode list : lists) {
if(list != null) {
queue.add(list);
}
}
while(!queue.isEmpty()) {
ListNode node = queue.poll();
if(node == null) {
continue;
}
cur.next = node;
cur = cur.next;
if(node.next != null) {
queue.offer(node.next);
}
}
return res.next;
}
}
自己方法：（超时）
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) {
//使用优先队列（小根堆）
PriorityQueue<ListNode> queue =
new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
ListNode res = new ListNode(0);
ListNode cur = res;
Iterator<ListNode> iter = lists.iterator();
while(iter.hasNext()) {
ListNode list = iter.next();
while(list != null) {
queue.add(list);
list = list.next;
}
}
while(!queue.isEmpty()) {
cur.next = queue.poll();
cur = cur.next;
}
return res.next;
}
}
最新文章
- LNMP环境搭建完整步骤
- 一个简单的游戏开发框架（四.舞台Stage）
- Linux学习笔记(18) Shell编程之流程控制
- Lua数据结构
- python函数应用
- Java虚拟机内存模型及垃圾回收监控调优
- oracle连接总结（内连接、外连接、自然连接，交叉连接，自连接）
- JAVA三大特性之多态
- js监听input等表单输入框的变化事件oninput
- CSDN博客导出工具 Mac By Swift
- J2那几个E和Web基础
- TCP/IP协议栈(三）——linux 向下的报文处理
- 安装新的int 9中断例程2
- MyISAM和InnoDB的索引实现
- C#遍历枚举中所有值
- js获取地址栏上参数的值
- C语言第八讲,指针*
- React项目中使用Mobx状态管理（二）
- StringBuffer 和 StringBuilder 类
- myeclipse 代码提示