Alkesh Ghorpade

Posted on May 21, 2023 • Originally published at alkeshghorpade.me

Merge k Sorted Lists - LeetCode

#leetcode #algorithms #programming #go

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/merge-k-sorted-lists

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.

Solutions for Merge k Sorted Lists Problem

Approach 1: Brute Force

In one of the previous blog posts, we discussed how to Sort a single Linked List. In this problem we need to merge K sorted Linked list.

A simple solution would be to connect all k linked lists into one list (in any order). Then use the merge sort algorithm discussed in Sort List post. The worst-case time complexity of this approach is O(n * log(n)), where n is the total number of nodes present in all the k lists. This approach is inefficient as we are not taking advantage of the already sorted lists.

Let's check the C++ snippet of this approach below:

ListNode* getLastNode(ListNode* head) {
    ListNode* current = head;
    ListNode* next = current->next;

    while(next != NULL) {
        current = next;
        next = current->next;
    }

    return current;
}

// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) {
        return NULL;
    }

    // connect all k sorted linked lists into one list
    for(int i = 0; i < lists.size() - 1; i++) {
        // fetch the last node
        ListNode* last = getLastNode(lists[i]);

        last->next = lists[i + 1];
    }

    // perform merge sort on list[0]
    return sortList(lists[0]);
}

// merge sort the two list
ListNode* mergelist(ListNode *l1, ListNode *l2) {
    ListNode *ptr = new ListNode(0);
    ListNode *current = ptr;

    while(l1 != NULL && l2 != NULL) {
        if(l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }

        current = current->next;
    }


    if(l1 != NULL) {
        current->next = l1;
        l1 = l1->next;
    }

    if(l2 != NULL) {
        current->next = l2;
        l2 = l2->next;
    }

    return ptr->next;
}

ListNode* sortList(ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;

    ListNode *temp = NULL;
    ListNode *slow = head;
    ListNode *fast = head;

    // split the list into two halves
    while(fast != NULL && fast->next != NULL) {
        temp = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    temp->next = NULL;

    // recursively call the sortList function for the two lists
    ListNode* l1 = sortList(head);
    ListNode* l2 = sortList(slow);

    // merge list l1 and l2
    return mergelist(l1, l2);
}

A second brute-force approach to solve the problem is by merging two sorted lists at a time. We merge the first two lists lists[0] with lists[1] and store the result. We merge the result with the third list lists[2] and repeat the process k - 1 time.

This method is relatively easy. But the time complexity of this approach is O(n * k), where n is the number of elements to be merged.

A C++ snippet of this approach is as below:

// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) {
        return NULL;
    }

    return mergeKSortedListsHelper(lists);
}

// Helper function to merge k sorted lists
ListNode* mergeKSortedListsHelper(vector<ListNode*>& lists) {
    int size = lists.size();

    // Traverse from the second list to last
    for (int i = 1; i <= size; i++) {
        while(true) {
            ListNode head1 = lists[0], head2 = lists[i];

            // if the list has ended
            if(head1 == NULL) {
                break;
            }

            if(head1->val >= head2->val) {
                lists[i] = head2->next;
                head2->next = head1;
                lists[0] = head2;
            } else {
                // Traverse the first list
                while (head1->next != NULL) {
                    // find the node in the first list which is just
                    // greater than second list current node
                    if (head1->next->val >= head2->val) {
                        lists[i] = head2->next;
                        head2->next = head1->next;
                        head1->next = head2;
                        break;
                    }

                    head1 = head1->next;
                }

                if(head1->next == NULL) {
                    lists[i] = head2->next;
                    head2->next = NULL;
                    head1->next = head2;
                    head1->next->next = NULL;
                    break;
                }
            }
        }
    }

    return lists[0];
}

The time complexity of the above two approaches is very high, as we are not taking advantage of the sorted lists. We can optimize the approach using an additional data structure: Min Heap.

Approach 2: Using Min Heap

We can optimize the above approach by using a Min Heap. The root of the Min Heap is always the smallest element.

As per the problem statement, all the linked lists are sorted. Therefore, the first element of the list will be the smallest. We add the first elements of all the linked lists into a Min Heap. We extract the smallest element, the Min Heap's root. After the root is removed, we increment the pointer of the list to which the root element belonged. The next node of this list is added to the Min Heap. We continue removing the root, and keep adding the next node from the lists to the heap until all the lists are traversed, and the heap is empty.

This algorithm can also be used to merge K sorted arrays. The time complexity of the algorithm is O(n * log(k)). Where n is the number of elements across all the lists and k is the number of linked lists. The space complexity is O(k) where k is the size of the Min Heap.

Let's check the algorithm for this approach.

- priority_queue<ListNode*, vector<ListNode*>, compare> pq

- for int i = 0; i < k; i++
  - if lists[i] != NULL
    - pq.push(arr[i])
  - if end
- for end

- if pq.empty()
  - return NULL
- if end

- ListNode* result = new ListNode(0)
  ListNode* last = dummp

- loop while !pq.empty()
  - ListNode* current = pq.top()
    pq.pop()

  - last->next = current
    last = last->next

  - if current->next != NULL
      pq.push(curr->next)
  - if end
- while end

- return result->next

Let's check the algorithm in C++ code.

ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> pq;
    int k = lists.size();

    // Push the first nodes of all the k lists in priority_queue 'pq'
    for (int i = 0; i < k; i++)
        if (lists[i] != NULL)
            pq.push(lists[i]);

    if (pq.empty())
        return NULL;

    ListNode *result = new ListNode(0);
    ListNode *last = result;

    // Loop till 'pq' is not empty
    while (!pq.empty()) {
        // Get the top element of 'pq'
        ListNode* current = pq.top();
        pq.pop();

        // Add the top element of 'pq' to the result list
        last->next = current;
        last = last->next;

        // If the current next node is not NULL, add it to the priority queue
        if (current->next != NULL) {
            pq.push(curr->next);
        }
    }

    // return the result
    return result->next;
}

Approach 3: Using Divide and Conquer

Using Min Heap, we reduced the time complexity to O(n * log(k)), but it takes O(k) extra space for the heap. We can solve this problem in constant space using Divide and Conquer technique.

As mentioned in our Brute force approach, we know how to merge two sorted lists. The idea is to pair up k lists and merge each pair in linear time using the O(1) space. After the first iteration, k/2 lists of size 2 * n are left. After the second cycle, k/4 lists are left. We repeat the procedure until we have one list left.

Let's check the algorithm first.

// function mergeKLists(vector<ListNode*>& lists)
- if lists.size() == 0
  - return NULL
- if end

- return mergeKListsHelper(lists, lists.size() - 1)

// function mergeKListsHelper(vector<ListNode*>& lists, int last)
// Merge lists until one list is left
- loop while last != 0
  - initilaize i = 0, j = last

  - loop while i < j
    // merge list i with list j
    // store the merged result in list i
    - lists[i] = mergeLists(lists[i], lists[j])

    - increment i = i++
    - decrement j = j--

    - if i >= j
      - last = j
    - if end
  - while end
- while end

- return lists[0]

// function mergeLists(ListNode* l1, ListNode* l2)
- set ListNode* head = NULL

- if l1 == NULL
  - return l2
- else if l2 == NULL
  - return l1
- if end

- if l1->val < l2->val
  - set head = l1
  - set l1 = l1->next
- else
  - set head = l2
  - set l2 = l2->next
- if end

- set ListNode* p = head

- loop while l1 && l2
  - if l1->val < l2->val
    - set p->next = l1
    - set l1 = l1->next
  - else
    - set p->next = l2
    - set l2 = l2->next
  - if end

  - set p = p->next
- while end

- if l1 != NULL
  - p->next = l1
- else
  - p->next = l2
- if end

- return head

The time complexity of the above approach is O(n * log(k)), and the space complexity is O(1).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) {
            return NULL;
        }

        return mergeKListsHelper(lists, lists.size() - 1);
    }

    ListNode* mergeKListsHelper(vector<ListNode*>& lists, int last) {
        // Merge lists until one list is left
        while(last != 0) {
            int i = 0, j = last;

            while(i < j) {
                // merge list i with list j
                // store the merged result in list i
                lists[i] = mergeLists(lists[i], lists[j]);

                i++;
                j--;

                // update last when all pairs are merged
                if(i >= j) {
                    last = j;
                }
            }
        }

        return lists[0];
    }

    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        ListNode* head = NULL;

        // if any one of the two lists is empty
        // return the other list.
        if(l1 == NULL) {
            return l2;
        } else if(l2 == NULL) {
            return l1;
        }

        // choose the head based on the smallest value of two lists.
        if(l1->val < l2->val){
            head = l1;
            l1 = l1->next;
        } else {
            head = l2;
            l2 = l2->next;
        }

        ListNode *p;
        p = head;

        while(l1 && l2){
            if(l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }

            p = p->next;
        }

        if(l1 != NULL){
            p->next = l1;
        } else {
            p->next = l2;
        }

        return head;
    }
};

Golang solution

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil;
    }

    return mergeKListsHelper(lists, len(lists) - 1)
}

func mergeKListsHelper(lists []*ListNode, last int) *ListNode {
    // Merge lists until one list is left
    for last != 0 {
        i, j := 0, last

        for(i < j) {
            // merge list i with list j
            // store the merged result in list i
            lists[i] = mergeLists(lists[i], lists[j])

            i++;
            j--;

            // update last when all pairs are merged
            if i >= j {
                last = j
            }
        }
    }

    return lists[0]
}

func mergeLists(l1, l2 *ListNode) *ListNode {
    var head *ListNode
    head = nil

    // if any one of the two lists is empty
    // return the other list.
    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    }

    // choose the head based on the smallest value of the two lists.
    if(l1.Val < l2.Val){
        head = l1;
        l1 = l1.Next;
    } else {
        head = l2;
        l2 = l2.Next;
    }

    p := head

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            p.Next = l1
            l1 = l1.Next
        } else {
            p.Next = l2
            l2 = l2.Next
        }

        p = p.Next
    }

    if l1 != nil {
        p.Next = l1
    } else {
        p.Next = l2
    }

    return head
}

JavaScript solution

var mergeKLists = function(lists) {
    if(lists.length === 0) {
        return null;
    }

    return mergeKListsHelper(lists, lists.length - 1);
};

var mergeKListsHelper = function(lists, last) {
    // Merge lists until one list is left
    while(last != 0) {
        let i = 0, j = last;

        while(i < j) {
            // merge list i with list j
            // store the merged result in list i
            lists[i] = mergeLists(lists[i], lists[j]);

            i++;
            j--;

            // update last when all pairs are merged
            if(i >= j) {
                last = j;
            }
        }
    }

    return lists[0];
};

var mergeLists = function(l1, l2) {
    let head = null;

    // if any one of the two lists is empty
    // return the other list.
    if(l1 == null) {
        return l2;
    } else if(l2 == null) {
        return l1;
    }

    // choose the head based on the smallest value of the two lists.
    if(l1.val < l2.val){
        head = l1;
        l1 = l1.next;
    } else {
        head = l2;
        l2 = l2.next;
    }

    let p = head;

    while(l1 && l2){
        if(l1.val < l2.val){
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }

        p = p.next;
    }

    if(l1 != null){
        p.next = l1;
    } else {
        p.next = l2;
    }

    return head;
};

Let's dry-run our algorithm to see how the solution works.

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

// mergeKLists function
Step 1: if lists.size() == 0
          3 == 0
          false

Step 2: return mergeKListsHelper(lists, lists.size() - 1)
               mergeKListsHelper(lists, 2)

// mergeKListsHelper
Step 3: loop while last != 0
          2 != 0
          true

          i = 0
          j = last
            = 2

          loop while i < j
            0 < 2
            true

            lists[i] = mergeLists(lists[i], lists[j])
            lists[0] = mergeLists(lists[0], lists[2])
                     = mergeLists([1, 4, 5], [2, 6])

// mergeLists([1, 4, 5], [2, 6])
Step 4: This function will merge the list and return
        [1, 2, 4, 5, 6]

// mergeKListsHelper
Step 5: i++
        i = 1

        j--
        j = 1

        if i >= j
           1 >= 1
           true

           last = j
           last = 1

        loop while i < j
          1 < 1
          false

// mergeKListsHelper
Step 6: loop while last != 0
          1 != 0
          true

          i = 0
          j = last
            = 1

          loop while i < j
            0 < 1
            true

            lists[i] = mergeLists(lists[i], lists[j])
            lists[0] = mergeLists(lists[0], lists[1])
                     = mergeLists([1, 2, 4, 5, 6], [1, 3, 4])

// mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
Step 7: This function will merge the list and return
        [1, 1, 2, 3, 4, 4, 5, 6]

// mergeKListsHelper
Step 8: i++
        i = 1

        j--
        j = 0

        if i >= j
           1 >= 0
           true

           last = j
           last = 0

        loop while i < j
          1 < 0
          false

Step 9: loop while last != 0
          0 != 0
          false

Step 10: return lists[0]
         [1, 1, 2, 3, 4, 4, 5, 6]

Top comments (1)

Kostas Kalafatis • May 24 '23

Hey there! Nice article!

While your implementations are correct, there are some optimizations you can make to your solutions.

On the C++ code:

In the mergeKLists function, instead of repeatedly merging pairs of lists until only one list is left, you can simplify the process by merging lists directly. You can iterate over the lists vector and merge each pair of adjacent lists, reducing the vector's size until only one merged list remains.

ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        while (lists.size() > 1) {
            int size = lists.size();
            int i = 0;
            while (i < size - 1) {
                lists[i] = mergeLists(lists[i], lists[size - 1]);
                lists.pop_back();
                i++;
                size--;
            }
        }

        return lists[0];
    }

In the mergeLists function, you can use a dummy node to simplify the code and eliminate the need for handling special cases. This node will serve as a starting point of the merged list, and you can use a curr pointer to track the current position during merging. You can also use a single loop and a ternary operation.

ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        while (lists.size() > 1) {
            int size = lists.size();
            int i = 0;
            while (i < size - 1) {
                lists[i] = mergeLists(lists[i], lists[size - 1]);
                lists.pop_back();
                i++;
                size--;
            }
        }

        return lists[0];
    }

Similar optimizations can be carried out to your Javascript solution.

Instead of repeatedly calling the mergeKListsHelper function recursively, you can use a while loop and merge the lists iteratively until only one list remains
Instead of updating the last variable to track the remaining lists, you can use the lists.length property, which eliminates the need for the last parameter.
You can use a while loop instead of a nested while loop to merge the lists.

var mergeKLists = function(lists) {
    if (lists.length === 0) {
        return null;
    }

    while (lists.length > 1) {
        let mergedLists = [];
        for (let i = 0; i < lists.length; i += 2) {
            const list1 = lists[i];
            const list2 = lists[i + 1];
            const merged = mergeLists(list1, list2);
            mergedLists.push(merged);
        }
        lists = mergedLists;
    }

    return lists[0];
};

In the mergeLists function, you can initialize a dummy node to simplify the merging process.
You can use a separate variable current to keep track of the current node while merging lists, eliminating the need of an additional p variable.

var mergeKLists = function(lists) {
    if (lists.length === 0) {
        return null;
    }

    while (lists.length > 1) {
        let mergedLists = [];
        for (let i = 0; i < lists.length; i += 2) {
            const list1 = lists[i];
            const list2 = lists[i + 1];
            const merged = mergeLists(list1, list2);
            mergedLists.push(merged);
        }
        lists = mergedLists;
    }

    return lists[0];
};

DEV Community

Merge k Sorted Lists - LeetCode

Problem statement

Solutions for Merge k Sorted Lists Problem

Approach 1: Brute Force

Approach 2: Using Min Heap

Approach 3: Using Divide and Conquer

C++ solution

Golang solution

JavaScript solution

Top comments (1)

Read next

GO:lack of synchronization

Goroutines and Channels: Concurrency Patterns in Go

Building deep-links in Electron application

Unlock the Power of Custom Formatting in Go: A Deep Dive into the Formatter Interface