Merge K Sorted Linked Lists

In this class, We discuss Merge K Sorted Linked Lists.

Readers can prepare an entire competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given K sorted linked lists.

Our task is to sort all k-linked lists and make one sorted list.

Time complexity: O(nklogk) n is the number of elements in the list containing maximum elements.

Space complexity: O(k)

Example:

L1: 1-2-3

L2: 4-5

L3: 5-6

L4: 7-8

Output: 1-2-3-4-5-5-6-7-8

arr=[L1, L2, L3, L4]

Logic:

Using min heap, we can easily solve in the given time.

The step-by-step explanation is provided in the video.

Code:

import heapq

class Solution:

    def kthLargest(self, k, arr, n):

        # code here

        list = []

        min=[]

        for val in arr:

            if len(min) < k:

                heapq.heappush(min, val)

            else:

                if val > min[0]:

                    heapq.heappop(min)

                    heapq.heappush(min, val)

            if len(min) >= k:

                list.append(min[0])

            else:

                list.append(-1)

        return list

arr = [1, 2, 3, 4, 5, 6]

ob=Solution()

res = ob.kthLargest(4,arr,len(arr))

for x in res:

    print(“Kth largest element is”, x)