23. Merge k Sorted Lists

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

Python

Heap Sort

Use the built-in heapq data structure

• Time: O(n)
• Space: O(n)

from heapq import heappush, heappop


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for head in lists:
            node = head
            while node:
                heappush(heap, node.val)
                node = node.next

        head = ListNode()
        node = head
        while heap:
            node.next = ListNode(val=heappop(heap))
            node = node.next

        return head.next

Forces Bust (Timeout)

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        head = ListNode()
        cur = head

        while any(lists):
            min_val = 10 ** 4
            min_index = None

            for index, head_node in enumerate(lists):
                if head_node is None:
                    continue

                if head_node.val < min_val:
                    min_index = index
                    min_val = head_node.val

            cur.next = ListNode(val=min_val)
            cur = cur.next
            lists[min_index] = lists[min_index].next

        return head.next

Javascript

var mergeKLists = function(lists) {
    if (lists.length === 0) return new ListNode().next;
    
    let result = lists[0];
    for (let i = 1; i < lists.length; i++) {
        result = mergeList(result, lists[i]);
    }
    return result;
};

var mergeList = function(list1, list2) {
    let head = new ListNode();
    let start = head;
    
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            start.next = list1;
            list1 = list1.next;
        } else {
            start.next = list2;
            list2 = list2.next;
        }
        start = start.next;
    }
    
    start.next = list1 === null ? list2 : list1;
    return head.next;
}