力扣合并K个排序链表
目录
力扣——合并K个排序链表
题目链接：
题目描述：
思路：
同步合并
已知顺序排列，每个链表的node比较再加进结果，用优先队列方便比较node，可以先把每个链表的头结点加进队列，然后队列头出，出来的头还有next，就加进去，这样确保每个链表都有节点放进队列里面了
两两合并
两两合并链表，逐个击破
实现代码：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);;
for(ListNode node : lists){
if (node != null) {
q.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(!q.isEmpty()){
cur.next = q.poll();
cur = cur.next;
if(cur.next != null){
q.offer(cur.next);
}
}
return dummy.next;
}
}class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
for(int i = 0; i < lists.length ; i++){
ans = merge(ans,lists[i]);
}
return ans;
}
public ListNode merge(ListNode a, ListNode b){
if(a == null || b== null){
return a != null ? a:b;
}
ListNode head = new ListNode(0);
ListNode cur = head, p1 = a, p2 = b;
while(p1 != null && p2 != null){
if(p1.val < p2.val){
cur.next = p1;
p1 = p1.next;
}else{
cur.next = p2;
p2 = p2.next;
}
cur = cur.next;
}
cur.next = p1 != null ? p1 : p2;
return head.next;
}
}