Merge K Sorted Lists

Understand how to merge multiple sorted singly linked lists into a single sorted list by applying k-way merge strategies. This lesson helps you develop efficient coding solutions and reinforces your grasp of sorting and linked list manipulation for interviews.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

You are given an array, lists, containing k singly linked lists. Each of these linked lists is individually sorted in ascending order.

Your task is to merge all k linked lists into a single sorted linked list in ascending order and return the merged list.

Constraints:

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

Examples

Merge K Sorted Lists

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

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

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

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

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

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

1 / 3

Java

usercode > Solution.java

// Definition for a Linked List node
// class ListNode {
//     int val;
//     ListNode next;
//     // Constructor
//     public ListNode(int val) {
//         this.val = val;
//         this.next = null;
//     }
// }
import ds_v1.LinkedList.ListNode;
import java.util.*;
class Solution {
	public static ListNode mergeKLists(ListNode[] lists) {
        
		// Replace this placeholder return statement with your code
		return null;
	}
}

Merge K Sorted Lists

Merge K Sorted Lists

Statement

Examples

Understand the problem

Figure it out!

Try it yourself