23.Merge_k_Sorted_Lists(Hard).md

23. Merge k Sorted Lists (Hard)

Date and Time: Aug 7, 2024, 16:22 (EST)

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

Question:

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 will not exceed 10^4.

Walk-through:

1. Base case when lists = [] or lists = [[]], we return None.

2. Loop over lists and merge two lists from lists each time and append the result to mergeList, so we can reset lists = mergedList. And we repeat to merge the new "merged" lists.

3. return lists[0] because lists is [something].

Python Solution:

# 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]:
        # Merge two lists each time, set lists = mergedList

        # TC: O(nlogk), n is total elements, k = len(lists), SC: O(n)
        if not lists:
            return None
        def merge(l1, l2):
            dummy = curr = ListNode()
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next
            # Add the remaining
            if l1 or l2:
                curr.next = l1 or l2
            return dummy.next
        
        while len(lists) > 1:
            mergedList = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if i+1 < len(lists) else None
                mergedList.append(merge(l1, l2))
            lists = mergedList
        return lists[0]

Time Complexity: $O(nlog\ k)$, we traverse all the n elements, and we are merging 2 lists each time, which takes $O(log\ k)$ for k lists.
Space Complexity: $O(n)$

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 {
    /* 
    1. Check lists is empty or not
    2. Merge two lists together into a tmp[]
    3. Reassign lists = tmp
    TC: O(nlogn), SC: O(n)
    */
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        // Check the rest of l1 and l2
        if (l1 != null) {
            curr.next = l1;
        } else if (l2 != null) {
            curr.next = l2;
        }
        return dummy.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // Check lists
        if (lists == null || lists.length == 0) {
            return null;
        }
        while (lists.length > 1) {
            List<ListNode> tmp = new ArrayList<>();
            // Merge two lists at the same time
            for (int i = 0; i < lists.length; i+=2) {
                ListNode l1 = lists[i];
                ListNode l2;
                if (i + 1 < lists.length) {
                    l2 = lists[i+1];
                } else {
                    l2 = null;
                }
                tmp.add(merge(l1, l2));
            }
            lists = tmp.toArray(new ListNode[0]);
        }
        return lists[0];
    }
}

C++ Solution:

1. condition ? result_if_true : result_if_false

2. .empty() to check length

3. If we initalize an object by ListNode dummy;, then we access its members by dummy.next using dot (.).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return NULL;
        }
        while (lists.size() > 1) {
            vector<ListNode*> mergedList;
            for (int i = 0; i < lists.size(); i += 2) {
                ListNode* l1 = lists[i];
                ListNode* l2 = (i + 1 < lists.size()) ? lists[i+1] : NULL;
                mergedList.push_back(merge(l1, l2, mergedList));
            }
            lists = mergedList;
        }
        return lists[0];   
    }

private:
    ListNode* merge(ListNode* l1, ListNode* l2, vector<ListNode*>& mergedList) {
        ListNode dummy; // dummy is an objects
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        // condition ? result_if_true : result_if_false
        tail->next = l1 ? l1: l2;
        return dummy.next;  // Cuz dummy is object, we access its members by dot.
    }
};