LeetCode #23: Merge k Sorted Lists — Solved in Java

Scan Across k Heads and Priority Queue

Image Source

LeetCode problem 23, Merge k Sorted Lists, asks you to merge multiple sorted linked lists into one sorted list. Each list is already sorted in non-decreasing order, and the output should preserve that ordering across all nodes from every list. The input comes as an array of list heads, and the job is to stitch them together into a single chain.

When solving this in Java, the first thought is how to always pick the smallest current node across all lists. That choice defines the next link in the merged chain. From there, two natural strategies appear. You can repeatedly scan all list heads and pick the smallest one each time, which is easy to code but slows down as the number of lists grows. Or you can let a data structure such as a priority queue handle the ordering for you, which keeps selection fast at the cost of some extra space. Both paths solve the problem, but the tradeoff between simplicity and efficiency guides which solution you write.

LeetCode: Merge k Sorted Lists

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 linked 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 <= 104

• 0 <= lists[i].length <= 500

• -104 <= lists[i][j] <= 104

• lists[i] is sorted in ascending order.

• The sum of lists[i].length will not exceed 104.

/**
 * 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; }
 * }
 */

Solution 1: Simple Scan Across k Heads

Start with a dummy node, keep a tail pointer, and at each step pick the smallest head among the k lists. Append it, advance that list’s pointer, repeat until all lists are empty. No extra structures beyond a few pointers, just a simple loop that always chooses the current minimum by scanning the heads.