Interview Prepin-place-linked-listhardAmazonFacebookGoogleMicrosoftBloomberg

Merge K Sorted Lists

Choose your preparation mode4 modes available

Try It Solution Trace

</>

IDE

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    # Write your solution here
    pass

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // Write your solution here
    return nullptr;
}

function mergeKLists(lists) {
    // Write your solution here
}

0/10

Common Bugs to Avoid

Wrong: Missing nodes or incomplete merged listNot processing all lists or stopping early when merging✅ Ensure all lists are pushed into the min-heap and all nodes are processed until heap is empty

Wrong: Output list missing duplicates or merged incorrectlySkipping nodes with equal values or merging duplicates incorrectly✅ Do not skip nodes with equal values; always push next nodes into the heap regardless of duplicates

Wrong: Crashes or returns non-null for empty inputNo check for empty input array or all empty lists✅ Add guard clauses to return null if input array is empty or all lists are empty

Wrong: Time limit exceeded (TLE)Using brute force sorting or repeated pairwise merges with O(kN) or O(N log N) complexity✅ Use a min-heap or divide and conquer merge to achieve O(N log k) time complexity

Wrong: Incorrect order due to greedy mergesMerging lists one by one greedily without balancing or heap✅ Use divide and conquer or min-heap to merge all lists efficiently and correctly

✓

Test Cases

t1_01basic

Input{"lists":[[1,4,5],[1,3,4],[2,6]]}

Expected"1->1->2->3->4->4->5->6"

Merging the three sorted lists results in one sorted list: 1->1->2->3->4->4->5->6

t1_02basic

Input{"lists":[[2,5,7],[3,11],[1,6,8,9]]}

Expected"1->2->3->5->6->7->8->9->11"

Merging three sorted lists results in 1->2->3->5->6->7->8->9->11

Practice

(1/5)

1. Identify the bug in the following code snippet intended to find the intersection node of two singly linked lists using the two-pointer approach:

medium

A. Line 6: Using '!=' instead of 'is not' to compare nodes

B. Line 8: Not checking if headA or headB is None before starting

C. Line 9: Incorrectly resetting pA and pB to headB and headA respectively

D. Line 10: Returning pA instead of pB

2. The following code attempts to merge two sorted linked lists in-place:

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            # BUG: Missing l1 pointer advancement here
        prev.next = l2
        l1, l2 = l2, l1
    return head

What is the bug in this code?

medium

A. Swapping l1 and l2 when l1.val > l2.val is incorrect

B. Not initializing prev before inner while loop causes NoneType error

C. Returning head instead of l1 or l2 at the end causes wrong output

D. Line missing advancement of l1 inside inner while loop causes infinite loop

3. Consider the following buggy code snippet for removing duplicates from a sorted linked list. Which line contains the subtle bug that causes incorrect removal of duplicates at the head of the list?

def deleteDuplicates(head):
    if not head or not head.next:
        return head
    prev = None
    current = head
    while current and current.next:
        if current.val == current.next.val:
            val_to_remove = current.val
            while current and current.val == val_to_remove:
                current = current.next
            if prev:
                prev.next = current
        else:
            prev = current
            current = current.next
    return head

medium

A. Line 3: prev initialized to null instead of dummy node.

B. Line 7: while loop condition should check current.next.val instead of current.val.

C. Line 11: Missing update of prev when duplicates are removed at head.

D. Line 14: prev pointer updated incorrectly inside else block.

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Merge K Sorted Lists

Practice

Solution

Step 1: Understand node comparison

Step 2: Identify correct comparison operator

Final Answer:

Quick Check:

Solution

Step 1: Identify the inner while loop behavior

Step 2: Confirm impact of missing advancement

Final Answer:

Quick Check:

Solution

Step 1: Identify problem with head duplicates

Step 2: Analyze code behavior

Final Answer:

Quick Check:

Solution

Step 1: Understand pointer updates

Step 2: Identify bug in pointer advancement

Final Answer:

Quick Check:

Solution

Step 1: Understand circular list implications

Step 2: Break the cycle

Step 3: Restore circular link if needed

Final Answer:

Quick Check:

Ready to prove it?