Skip to main content

Leetcode 23: Merge k Sorted Lists

 

1. Problem Statement (Simple Explanation):


You are given an array lists of k sorted linked lists.

  • Each lists[i] is the head of a singly linked list, sorted in ascending order.

  • You need to merge all k lists into one sorted linked list.

  • Return the head of the merged list.

Edge cases:

  • lists can be empty (k = 0) → return [].

  • Some lists may be empty (lists[i] == null).


2. Examples:


Example 1:

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

These represent:

  • List 1: 1 → 4 → 5

  • List 2: 1 → 3 → 4

  • List 3: 2 → 6

Merged:

1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Output: [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

  • Total number of nodes across all lists <= 104

  • Each list is sorted in ascending order.


3. Approach 1 – Pairwise Merge (Divide & Conquer, O(N log k), Recommended):


This problem is a k-way merge of sorted lists. A natural strategy:

  • Repeatedly merge two sorted lists at a time (like LeetCode 21).

  • Use a divide & conquer strategy to reduce complexity.


Intuition:


This is analogous to merging k sorted arrays:

  1. Merge lists in pairs:

    • Round 1: merge pairs (0,1), (2,3), (4,5), ...

    • Round 2: merge resulting lists again in pairs, etc.

  2. Each node participates in O(log k) merge levels.

Let:

  • N = total number of nodes across all lists.

Time complexity: O(Nlogk)

Space (extra): O(1)

excluding recursion stack if done iteratively, or O(logk) with recursive divide & conquer.


Helper – Merge Two Sorted Lists:


Same as problem 21:



Strategy A – Iterative Merge (Bottom-up):


  1. If lists is empty, return null.

  2. While lists.length > 1:

    • Create a new list mergedLists.

    • For every pair of lists (lists[i], lists[i+1]):

      • Merge them with mergeTwoLists.

      • Append result to mergedLists.

    • If odd number of lists, carry the last one forward.

    • Set lists = mergedLists.

  3. Return lists[0] (the only remaining list).


Pseudo-code (Iterative Pairwise Merge):



4. Approach 2 – Min-Heap (Priority Queue, O(N log k)):


Another common method uses a min-heap (priority queue):

  1. Push the head of each non-empty list into a min-heap, keyed by node value.

  2. Repeatedly:

    • Pop the smallest node from the heap.

    • Append it to the result list.

    • If that node has a next, push next into the heap.

  3. Continue until the heap is empty.


Complexity:


  • Each of the N nodes is pushed & popped once.

  • Each heap operation is O(log k).

So total time: O(Nlogk), extra space: O(k) for the heap.

Both divide & conquer and heap are good. For simplicity in teaching, the pairwise merge leverages an already-known helper (mergeTwoLists).


5. Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more