Merging K - Sorted Linked Lists

Problem Statement

Given k sorted linked lists, each containing sorted nodes, the task is to merge these lists into a single sorted linked list. For instance, if you have the following lists:

• List 1: 1 → 4 → 5

• List 2: 1 → 3 → 4

• List 3: 2 → 6

The merged result should be:

• Merged List: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Approach - 1

The approach to solve this problem involves two main steps:

1. Merging Two Sorted Lists: This is a fundamental operation where we merge two sorted linked lists into a single sorted linked list.

2. Merging Multiple Lists Using Divide and Conquer: We use the divide-and-conquer strategy to merge multiple lists efficiently. This involves merging pairs of lists iteratively until only one list remains.

Implementation

1. The mergeTwoLists function

/*
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}
*/

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let i = list1;
    let j = list2;
    let dummy = new ListNode(-1); 
    let tempLL = dummy;

    while (i !== null && j !== null) {
        if (i.val <= j.val) {
            tempLL.next = new ListNode(i.val);
            i = i.next;
        } else {
            tempLL.next = new ListNode(j.val);
            j = j.next;
        }
        tempLL = tempLL.next;
    }

    // Append remaining nodes, if any
    if (i !== null) {
        tempLL.next = i;
    } else {
        tempLL.next = j;
    }

    return dummy.next;
}

How It Works:

• Start with a Dummy Node: We use a dummy node to build the new list.

• Compare and Add Nodes: Look at both lists and add the smaller value to the new list. Move to the next node in the list where the value was taken.

• Add Remaining Nodes: If one list runs out of nodes, just add the rest of the other list.

• Return the Merged List: Skip the dummy node and return the start of the merged list.

2. The mergeKLists function

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (lists.length === 0) return null;
    if (lists.length === 1) return lists[0];

    while (lists.length > 1) {
        let mergedLists: Array<ListNode | null> = [];

        for (let i = 0; i < lists.length; i += 2) {
            const l1 = lists[i];
            const l2 = i + 1 < lists.length ? lists[i + 1] : null;
            mergedLists.push(mergeTwoLists(l1, l2));
        }

        lists = mergedLists;
    }

    return lists[0];
}

How It Works:

• Handle Simple Cases: If there are no lists, return nothing. If there's just one list, return it as is.

• Merge in Pairs: Merge the lists two at a time until only one list is left.

  • Pair Lists: Take pairs of lists and merge them using the mergeTwoLists function.

  • Update List of Lists: Replace the old lists with the new merged lists.

• Return the Final List: The last remaining list is the fully merged list.

Time Complexity Analysis

The time complexity of merging k sorted linked lists can be analyzed as follows:

1. Number of Merging Steps:

   • In each step, the number of lists is halved. The number of steps required to reduce k lists to 1 is

     $$\log_2 k$$

2. Work Done Per Step:

   • Each merging step involves merging lists where the total number of elements across all lists is N. Thus, each step processes all N elements.

Hence we get

$$O(N) \text{ (work per level)} \times O(\log_2 k) \text{ (number of levels)} = O(N \log k)$$

Alternative Approach

There’s another approach to solving the problem of merging multiple sorted linked lists, which involves using a data structure called a heap (or priority queue). This approach can be more efficient in some cases, especially when dealing with a large number of lists. I’ll cover this alternative method in detail in a future post when we dive into topics like heaps.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase