Merge K Sorted Lists

▶

Steps

setup

Initialize lists array

We start with the input array of three sorted linked lists: [1->4->5], [1->3->4], and [2->6]. This array is the starting point for merging.

💡 Initializing the array of lists is essential because the algorithm merges these lists pairwise until one remains.

Line:

lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]

💡 The problem reduces to merging these multiple sorted lists into one sorted list.

expand

Start first merge interval = 1

Set interval to 1 to merge lists in pairs: merge lists[0] with lists[1], then lists[2] remains alone.

💡 Interval controls the size of pairs to merge; starting with 1 means merging adjacent pairs.

Line:

interval = 1
while interval < len(lists):

💡 The algorithm merges pairs of lists at increasing intervals to reduce the number of lists.

merge

Merge lists[0] and lists[1] - start

Begin merging the first two lists: [1->4->5] and [1->3->4]. Compare their head nodes to pick the smaller value.

💡 Merging two lists is the core operation; comparing head nodes decides which node to add next.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 The smallest head node between the two lists is chosen to maintain sorted order.

compare

Compare heads: 1 vs 1, pick second list's node

Both lists have head value 1. The algorithm picks the node from the second list (lists[1]) and advances its pointer.

💡 When values are equal, the algorithm consistently picks from the second list to maintain stability.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next
else:
    current.next = l2
    l2 = l2.next

💡 The else branch is taken when values are equal or l2 is smaller, ensuring correct order.

traverse

Advance pointers in mergeTwoLists

Advance the pointer in the second list (lists[1]) to its next node (3), preparing for the next comparison.

💡 Advancing pointers moves through the lists, progressively building the merged list.

Line:

l2 = l2.next

💡 Pointer movement is essential to traverse and merge all nodes.

compare

Compare heads: 1 vs 3, pick first list's node

Now comparing 1 (lists[0]) and 3 (lists[1]), the smaller value 1 from lists[0] is chosen and its pointer advances.

💡 Choosing the smaller head node keeps the merged list sorted.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The algorithm always picks the smaller node to maintain order.

traverse

Advance pointer in first list after picking 1

Advance the pointer in the first list (lists[0]) to its next node (4) for the next comparison.

💡 Moving pointers forward is how the algorithm progresses through the lists.

Line:

l1 = l1.next

💡 Pointer advancement is key to eventually exhausting both lists.

compare

Compare heads: 4 vs 3, pick second list's node

Comparing 4 (lists[0]) and 3 (lists[1]), the smaller 3 from lists[1] is chosen and its pointer advances.

💡 The algorithm picks the smaller node to maintain sorted order in the merged list.

Line:

else:
    current.next = l2
    l2 = l2.next

💡 Choosing the smaller node from either list keeps the merged list sorted.

traverse

Advance pointer in second list after picking 3

Advance the pointer in the second list (lists[1]) to its next node (4) for the next comparison.

💡 Advancing pointers moves the merge process forward.

Line:

l2 = l2.next

💡 Each pointer movement brings the merge closer to completion.

insert

Merge remaining nodes and update lists array

Finish merging lists[0] and lists[1] into one sorted list: 1->1->3->4->4->5. Update lists[0] with this merged list.

💡 Replacing the pair with the merged list reduces the number of lists to merge.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 Merging pairs reduces problem size, moving towards the final merged list.

expand

Double interval to 2 and prepare next merge

Increase interval to 2 to merge lists[0] and lists[2] (if exists). Now only two lists remain: merged list and [2->6].

💡 Increasing interval merges larger pairs, eventually merging all lists into one.

Line:

interval *= 2

💡 Doubling interval controls the merge granularity.

merge

Merge lists[0] and lists[1] (merged list and [2->6]) - start

Begin merging the merged list [1->1->3->4->4->5] with [2->6]. Compare their head nodes to pick the smaller value.

💡 Final merge combines the two remaining lists into the fully sorted list.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 The final merge produces the complete sorted list.

compare

Compare heads: 1 vs 2, pick first list's node

Comparing 1 (merged list) and 2 ([2->6]), pick 1 from merged list and advance its pointer.

💡 Picking the smaller node keeps the merged list sorted.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The algorithm continues to pick the smallest node at each step.

traverse

Advance pointer in merged list after picking 1

Advance pointer in merged list to next node (1) for next comparison.

💡 Pointer movement is how the merge progresses through nodes.

Line:

l1 = l1.next

💡 Each advancement brings the merge closer to completion.

compare

Compare heads: 1 vs 2, pick first list's node again

Compare 1 (merged list) and 2 ([2->6]), pick 1 from merged list and advance pointer.

💡 Continuing to pick the smaller node maintains order.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The merge continues smoothly picking smallest nodes.

traverse

Advance pointer in merged list after picking 1

Advance pointer in merged list to next node (3) for next comparison.

💡 Pointer movement is essential to progress.

Line:

l1 = l1.next

💡 Advancing pointers moves the merge forward.

compare

Compare heads: 3 vs 2, pick second list's node

Compare 3 (merged list) and 2 ([2->6]), pick 2 from second list and advance pointer.

💡 Picking the smaller node from either list keeps order.

Line:

else:
    current.next = l2
    l2 = l2.next

💡 The algorithm correctly picks the smaller node from the second list.

traverse

Advance pointer in second list after picking 2

Advance pointer in second list to next node (6) for next comparison.

💡 Pointer movement is how the merge progresses.

Line:

l2 = l2.next

💡 Advancing pointers moves the merge closer to completion.

insert

Finish merging and update lists array

Finish merging all nodes into one sorted list: 1->1->2->3->4->4->5->6. Update lists[0] with this final merged list.

💡 The final merged list is the answer to the problem.

Line:

return lists[0]

💡 The algorithm successfully merges all lists into one sorted list.

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)  # STEP 3
    current = dummy
    while l1 and l2:  # STEP 4-18
        if l1.val < l2.val:  # STEP 6, 13, 15
            current.next = l1
            l1 = l1.next  # STEP 7, 14, 16
        else:
            current.next = l2
            l2 = l2.next  # STEP 5, 9, 18
        current = current.next
    current.next = l1 if l1 else l2  # STEP 10, 19
    return dummy.next

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:  # STEP 1
        return None
    interval = 1  # STEP 2
    while interval < len(lists):  # STEP 2
        for i in range(0, len(lists) - interval, interval * 2):  # STEP 3
            lists[i] = mergeTwoLists(lists[i], lists[i + interval])  # STEP 3-19
        interval *= 2  # STEP 11
    return lists[0]  # STEP 19

if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]  # STEP 1
    merged = mergeKLists(lists)  # STEP 2-19
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

📊

Merge K Sorted Lists - Watch the Algorithm Execute, Step by Step

Watching each merge operation and how the lists are combined helps you understand the divide and conquer approach clearly, beyond just reading code.

setupmin-heap

1

0

1

1

2

2

expandmin-heap

1

0

1

1

2

2

mergemin-heap

1

0

1

1

2

2

comparemin-heap

1

0

1

1

2

2

traversemin-heap

1

0

3

1

2

2

comparemin-heap

4

0

3

1

2

2

traversemin-heap

4

0

3

1

2

2

comparemin-heap

4

0

4

1

2

2

traversemin-heap

4

0

4

1

2

2

insertmin-heap

1

0

2

1

expandmin-heap

1

0

2

1

mergemin-heap

1

0

2

1

comparemin-heap

1

0

2

1

traversemin-heap

1

0

2

1

comparemin-heap

3

0

2

1

traversemin-heap

3

0

2

1

comparemin-heap

3

0

6

1

traversemin-heap

3

0

6

1

insertmin-heap

1

0

Added: "1->1->2->3->4->4->5->6"

Key Takeaways

✓ The divide and conquer approach merges pairs of lists repeatedly, reducing the problem size exponentially.

This insight is hard to see from code alone because the interval doubling and pairwise merges are subtle.

✓ Merging two sorted lists by comparing head nodes ensures the merged list remains sorted at every step.

Visualizing each comparison and pointer movement clarifies how the merge maintains order.

✓ Pointer advancement in each list is crucial to progress through the lists and complete the merge.

Watching pointer moves step-by-step reveals the mechanics behind the merge, which code alone can obscure.

Practice

1. Consider the following code snippet for adding two numbers represented by linked lists in-place. Given l1 = [2,4,3] and l2 = [5,6,4], what is the value of the node pointed to by prev after the second iteration of the while loop?

easy

A. 0

B. 7

C. 1

D. 9

Solution

1. Step 1: Trace first iteration

   Sum 2 + 5 + 0 = 7, carry=0, l1.val=7, prev points to node with val=7.

2. Step 2: Trace second iteration

   Sum 4 + 6 + 0 = 10, carry=1, l1.val=0, prev updated to node with val=0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After second iteration, prev.val is 0 [OK]

Hint: Carry affects node value update each iteration [OK]

Common Mistakes:

• Off-by-one error in updating prev
• Ignoring carry in sum calculation
• Confusing l1 and l2 pointers

2. You are given a singly linked list and need to determine if it reads the same forwards and backwards without using extra space proportional to the list size. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the linked list to an array and check if the array is a palindrome.

B. Use a dynamic programming approach to store palindrome states for sublists.

C. Use a recursive two-pointer technique that compares nodes from front and back simultaneously.

D. Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking palindrome property in a linked list without using extra space proportional to the list size, ruling out array conversion.

2. Step 2: Analyze space and time complexity of options

   Convert the linked list to an array and check if the array is a palindrome. uses O(n) extra space for array; Use a dynamic programming approach to store palindrome states for sublists. uses O(n^2) time and space; Use a recursive two-pointer technique that compares nodes from front and back simultaneously. uses O(n) time but O(n) space due to recursion stack; Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. uses O(n) time and O(1) space by reversing the second half and comparing.

3. Step 3: Identify optimal approach

   Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. is optimal with O(n) time and O(1) space, meeting constraints without recursion overhead.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Greedy pairwise comparison with in-place reversal is optimal [OK]

Hint: In-place reversal of second half achieves O(1) space palindrome check [OK]

Common Mistakes:

• Assuming recursion uses no extra space
• Confusing DP with palindrome linked list
• Thinking array conversion is space optimal

3. What is the space complexity of the recursive approach to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(n) -- due to recursion stack frames for each node

C. O(log n) -- recursion depth is logarithmic due to divide and conquer

D. O(n) -- due to auxiliary arrays used to store node references

Solution

1. Step 1: Identify recursion depth

   Recursion visits each node once, so recursion stack depth is n.

2. Step 2: Analyze space usage

   No extra arrays or data structures are used, but recursion stack frames consume O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space grows linearly with list length [OK]

Hint: Recursion stack space equals max call depth [OK]

Common Mistakes:

• Assuming constant space for recursion
• Confusing recursion with iterative approach
• Thinking recursion depth is logarithmic

4. What is the space complexity of the tail-recursive reversal approach for reversing a singly linked list of length n, and why might a common misconception about it be incorrect?

medium

A. O(1) because the reversal is done in-place with constant extra pointers.

B. O(n) because the recursion stack grows linearly with the list length.

C. O(n) because an auxiliary array is used to store nodes during reversal.

D. O(log n) because tail recursion optimizes the stack usage to logarithmic depth.

Solution

1. Step 1: Identify recursion stack usage

   Each recursive call adds a frame to the call stack until the base case is reached, so for n nodes, stack depth is n.

2. Step 2: Analyze auxiliary space

   No extra arrays or data structures are used, so auxiliary space besides recursion stack is O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursion stack causes O(n) space, not constant [OK]

Hint: Recursion stack adds O(n) space despite in-place pointer changes [OK]

Common Mistakes:

• Assuming tail recursion is optimized to O(1) stack in Python
• Confusing auxiliary data structures with recursion stack

5. Suppose the problem is extended so that the input linked lists can be reused multiple times in different additions without modification. Which modification to the optimal recursive solution is necessary to ensure correctness and input integrity?

hard

A. Use stacks to simulate reverse traversal without modifying input lists or copying.

B. Create deep copies of input lists before padding and addition to avoid modifying original lists.

C. Modify the recursive function to add digits without padding or copying.

D. Reverse the input lists in-place before addition to simplify logic.

Solution

1. Step 1: Understand input reuse constraint

   Input lists must remain unmodified for reuse, so in-place reversal or padding that changes nodes is disallowed.

2. Step 2: Identify approach preserving input integrity

   Using stacks to simulate reverse traversal reads digits from least significant to most significant without modifying or copying the lists.

3. Step 3: Compare alternatives

   Reversing in-place breaks input reuse; copying is expensive; recursion without padding fails alignment.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stacks preserve input and allow correct addition [OK]

Hint: Stacks simulate reverse without input mutation [OK]

Common Mistakes:

• Reversing input lists modifies them
• Copying inputs is costly and unnecessary
• Ignoring alignment leads to wrong sums