MrainW's Home

All things come to those who wait!

0%

LeetCode 23. Merge k Sorted Lists

Question

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

https://leetcode.com/problems/merge-k-sorted-lists/

  • Solution1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
//pq,time O(nlogk), space O(K)
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
ListNode dummy = new ListNode(0);
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (int i = 0; i < lists.length; i++)
if (lists[i] != null) pq.offer(lists[i]);//only first element will be insert to the pq
ListNode cur = dummy;
while(!pq.isEmpty()){
cur.next = pq.poll();
cur = cur.next;
if (pq.isEmpty()) break; //last cycle dont need work
if (cur.next != null) pq.offer(cur.next);
}
return dummy.next;
}
}

Complexity:

Time complexity: O(nklogk)

Space complexity: O(k)

Welcome to my other publishing channels