23-merge-k-sorted-lists

Try it on leetcode

Description

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 <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

Solution(Python)

from queue import PriorityQueue

# 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]:
        return self.spaceoptmized(lists)

    """
    traverse all nodes and store them in array
    sort the array 
    create the sorted linkedlist
    Time Complexity: O(n log n)
    Space Complexity: O(n)
    """

    def bruteforce(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        sortedvals = []
        for list in lists:
            while list:
                sortedvals.append(list.val)
                list = list.next

        DummyNode = cur = ListNode(-1)
        sortedvals.sort()
        for val in sortedvals:
            cur.next = ListNode(val)
            cur = cur.next
        return DummyNode.next

    """
    we can optmize bruteforce approach if we put our kth node with prioirty of its value in a priority queue and we can access the smallest value in O(1)
    
    Time Complexity: O(nlogk)
    Space Complexity: O(n)
    """

    def timeoptmized(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ListNode.__lt__ = lambda self, other: self.val < other.val
        Res = cur = ListNode(-1)
        q = PriorityQueue()
        for lst in lists:
            if lst:
                q.put((lst.val, lst))

        while not q.empty():
            val, node = q.get()
            cur.next = ListNode(val)
            cur = cur.next
            node = node.next
            if node:
                q.put((node.val, node))

        return Res.next

    """
    merging  a two sorted list can be done with constant space
    
    what if we keep on merging the adjacent pairs until it becomes a single sorted lists
    at each step the count of lists reduced into half atnost atmost log2k of such iterations need for each interation we got n values to traverse 
    
    Time Complexity: O(nlogk)
    Space Complexity: O(1)
    
     """

    def spaceoptmized(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        interval = 1

        while interval < k:
            for i in range(0, k - interval, 2 * interval):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
            interval *= 2

        return lists[0] if k > 0 else None

    def mergeTwoLists(self, lst1, lst2):
        sortedlst = cur = ListNode(-1)

        while lst1 and lst2:
            if lst1.val <= lst2.val:
                cur.next = lst1
                lst1 = lst1.next
            else:
                cur.next = lst2
                lst2 = lst2.next
            cur = cur.next
        if not lst1:
            cur.next = lst2
        else:
            cur.next = lst1
        return sortedlst.next