Merge K Sorted Lists

Try to solve the Merge K Sorted Lists problem.

We'll cover the following

Statement#

Given an array of kk sorted linked lists, your task is to merge them into a single sorted linked list and return the head of this linked list.

Constraints:

  • k=k = lists.length
  • 0≤k≤1030 \leq k \leq 10^3
  • 0≤0 \leq lists[i].length ≤500\leq 500
  • −103≤-10^3 \leq lists[i][j] ≤103\leq 10^3
  • Each lists[i] is sorted in ascending order.
  • The sum of all lists[i].length will not exceed 10310^3.

Example#

Created with Fabric.js 3.6.6 head 1 2 3 4 5 6 7 8 head 1 head 2 3 5 7 4 6 8 Output Sample example 1Input

1 of 2

Created with Fabric.js 3.6.6 head -1 head 2 24 35 97 6 19 head -1 2 35 97 24 6 19 Output Sample example 2Input

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Merge K Sorted Lists

1

What is the output if the following array is given as input?

lists = [
               head → 1 → 2 → 3 → NULL,
               head → 12 → 56 → 200 → NULL,
               head → -10 → -2 → 5 → NULL
            ]

A)

head → 1 → 2 → 3 → 12 → 56 → 200 → -10 → -2 → 5 → NULL

B)

head → 1 → 2 → 3 → -10 → -2 → 5 → 12 → 56 → 200 → NULL

C)

head → -10 → -2 → 1 → 2 → 3 → 5 → 12 → 56 → 200 → NULL

D)

head → -10 → -2 → 5 → 1 → 2 → 3 → 12 → 56 → 200 → NULL

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Traverse the input lists in pairs using head pointers.

Compare the node values of lists in each pair and add the smaller one to a dummy list.

Repeat the above steps until all the values from the lists in a pair are added.

Compare this new list with the resultant list of the next pair.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided a useful code template in the other file, that you may build on to solve this problem.

Python
main.py
linked_list_node.py
linked_list.py
linked_list_reversal.py
linked_list_traversal.py
Input #1
Merge K Sorted Lists

Solution: Kth Smallest Number in M Sorted Lists

Solution: Merge K Sorted Lists