Solved! Leetcode 23. Merge k Sorted Lists

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

Merge k Sorted Lists

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.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.

Java

/**
 * 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) {
        //Min Heap
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for(int i=0;i<lists.length;i++){
            if(lists[i]!=null)
                pq.add(lists[i]);
        } 
        //head of merged linkedlist initialized with -1
        ListNode head = new ListNode(-1);
        ListNode p = head;

        while(!pq.isEmpty()){
            ListNode n = pq.poll();
            //if the next pointer pointing to a non-null node add it to the heap
            if(n.next!=null){
                pq.add(n.next);
            }
            //unset the next pointer
            n.next = null;

            //add this node at the end of the meregd list and update pointer p
            p.next = n;
            p = p.next;
        }

        return head.next;
    }
}

/**

* 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) {

//Min Heap

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

for(int i=0;i<lists.length;i++){

if(lists[i]!=null)

pq.add(lists[i]);

}

//head of merged linkedlist initialized with -1

ListNode head = new ListNode(-1);

ListNode p = head;

while(!pq.isEmpty()){

ListNode n = pq.poll();

//if the next pointer pointing to a non-null node add it to the heap

if(n.next!=null){

pq.add(n.next);

}

//unset the next pointer

n.next = null;

//add this node at the end of the meregd list and update pointer p

p.next = n;

p = p.next;

}

return head.next;

}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        head = None

        heap = []
        setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)
        for node in lists:
            while node:
                nextNode = node.next
                node.next = None
                heapq.heappush(heap, (node.val, node))
                node = nextNode
        #print(heap)
        if heap:
            head = heapq.heappop(heap)[1]
        temp = head
        while heap:
            temp.next = heapq.heappop(heap)[1]
            temp = temp.next
        #print(head)
        return head

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

if not lists:

return None

head = None

heap = []

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

for node in lists:

while node:

nextNode = node.next

node.next = None

heapq.heappush(heap, (node.val, node))

node = nextNode

#print(heap)

if heap:

head = heapq.heappop(heap)[1]

temp = head

while heap:

temp.next = heapq.heappop(heap)[1]

temp = temp.next

#print(head)

return head

Time Complexity

Let’s the size of the lists is m
Let’s the size of each LinkedList (lists[i]) is n
At any point of time the size of the min heap will be m or less
To populate the min heap -> O(mlogm)
remove a node from the min heap -> O(1) * n -> O(n)
Add a new node n-times to the min heap -> O(nlogm)
total -> O(mlogm + n + nlogm) -> O(nlogm)

Space Complexity

O(m): size of the min heap

Rate this post

Coddicted