merge_k_sorted_ll.py

'''
Merge K Sorted Linked Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

=========================================
Using Priority Queue (heap) in each step chose the smallest element from the lists and add it to the result list.
    Time Complexity: 	O(N * LogK)  , LogK is for adding and deleting from Priority queue
    Space Complexity: 	O(N)
Using Divide and Conquer, similar to Merge sort.
    Time Complexity:    O(N * LogK)
    Space Complexity:   O(1)  , (using the same old list)
'''


##############
# Solution 1 #
##############

# import ListNode class from ll_helpers.py
from ll_helpers import ListNode

import heapq

# priority queue comparator class
class PQNode:
    def __init__(self, node):
        self.val = node.val
        self.node = node

    def __lt__(self, other):
        return self.val < other.val

# priority queue
class PriorityQueue:
    def __init__(self):
        self.data = []

    def push(self, node):
        heapq.heappush(self.data, PQNode(node))

    def pop(self):
        return heapq.heappop(self.data).node

    def is_empty(self):
        return len(self.data) == 0

def merge_k_lists_1(lists):
    heap = PriorityQueue()

    # add all linked lists in the heap
    for node in lists:
        if node is not None:
            heap.push(node)

    result = ListNode(-1)
    pointer = result

    while not heap.is_empty():
        # in each step remove the min list from the heap
        node = heap.pop()

        # add the min list to the result
        pointer.next = node
        pointer = pointer.next

        node = node.next
        if node is not None:
            # take the next node from the min list and add it in the heap
            heap.push(node)

    return result.next


##############
# Solution 2 #
##############

def merge_k_lists_2(lists):
    n = len(lists)
    if n == 0:
        return None

    # the step tells with which linked list should be merged the current linked list
    step = 1

    # divide and conquer without recursion
    while step < n:
        i = 0

        while i + step < n:
            lists[i] = merge_2_lists(lists[i], lists[i + step])
            # go to the next pair
            i += 2 * step

        # double the step
        step *= 2

    return lists[0]

def merge_2_lists(l1, l2):
    result = ListNode(-1)
    pointer = result

    while (l1 is not None) and (l2 is not None):
        if l1.val < l2.val:
            pointer.next = l1
            l1 = l1.next
        else:
            pointer.next = l2
            l2 = l2.next

        pointer = pointer.next

    if l1 is not None:
        pointer.next = l1

    if l2 is not None:
        pointer.next = l2

    return result.next