Merge Two Sorted Lists

📋

Merge Two Sorted Lists

Edge cases:

</>

IDE

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:public ListNode mergeTwoLists(ListNode l1, ListNode l2)ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)function mergeTwoLists(l1, l2)

def mergeTwoLists(l1, l2):
    # Write your solution here
    pass

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // Write your solution here
    return nullptr;
}

function mergeTwoLists(l1, l2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3,4]Skipping nodes from one list after the other list is exhausted.✅ After main merge loop, append the remaining nodes of the non-empty list to the merged list.

Wrong: [1,1,2,3,4]Incorrectly merging nodes with equal values by skipping duplicates.✅ Always link nodes even if values are equal, do not skip or merge duplicates.

Wrong: Stack overflow or timeout on large inputsUsing recursive merge causing stack overflow or exponential time on large inputs.✅ Use iterative merge with dummy head and two pointers to achieve O(n+m) time and O(1) space.

Wrong: Null or empty output when one list is non-emptyNot handling empty list inputs correctly, returning null instead of non-empty list.✅ Check if one list is empty and return the other list immediately.

✓

Test Cases

Try testing your code with empty and single-element lists to catch base case bugs.

Test with lists having equal elements and interleaved values to catch logic errors.

Use large inputs to verify your solution runs efficiently within time limits.

t1_01basic

Input{"l1":[1,2,4],"l2":[1,3,4]}

Expected[1,1,2,3,4,4]

⏱ Performance - must finish in 2000ms

We pick nodes from both lists in sorted order: 1 from list1, then 1 from list2, then 2 from list1, then 3 from list2, then 4 from list1, then 4 from list2.

💡 Try merging by comparing the heads of both lists repeatedly.

💡 Use two pointers to traverse both lists and pick the smaller node each time.

💡 Use a dummy head node to simplify edge cases and link nodes in sorted order.

Why it failed: Output is incorrect because nodes are not merged in sorted order. Fix by always choosing the smaller current node from l1 or l2 and linking it next.

✓ Correctly merges two sorted lists by comparing nodes and linking in order.

t1_02basic

Input{"l1":[2,5,7],"l2":[1,3,6,8]}

Expected[1,2,3,5,6,7,8]

⏱ Performance - must finish in 2000ms

Merged list contains all nodes from both lists in sorted order: 1,2,3,5,6,7,8.

💡 Check the first nodes of both lists to decide which to link first.

💡 Continue merging by always linking the smaller node and advancing that list's pointer.

💡 Remember to link the remaining nodes after one list is exhausted.

Why it failed: Incorrect output due to not linking remaining nodes after one list ends. Fix by appending the non-empty list at the end.

✓ Successfully merges lists including when lengths differ.

t2_01edge

Input{"l1":[],"l2":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Both input lists are empty, so the merged list is also empty.

💡 Consider what happens when both input lists are empty.

💡 Check if your code handles null or empty list inputs correctly.

💡 Return null or empty list immediately if both inputs are empty.

Why it failed: Fails to handle empty input lists, returning non-empty or error. Fix by checking if both lists are empty and returning empty list.

✓ Correctly returns empty list when both inputs are empty.

t2_02edge

Input{"l1":[5],"l2":[]}

Expected[5]

⏱ Performance - must finish in 2000ms

One list is empty, so the merged list is just the non-empty list.

💡 Check if your code handles one empty list and one non-empty list correctly.

💡 Make sure to return the non-empty list immediately if the other is empty.

💡 Avoid unnecessary processing when one list is empty.

Why it failed: Fails to return the non-empty list when the other is empty, possibly returning null or empty. Fix by returning the non-empty list if the other is empty.

✓ Correctly returns the non-empty list when the other is empty.

t2_03edge

Input{"l1":[2,2,2],"l2":[2,2]}

Expected[2,2,2,2,2]

⏱ Performance - must finish in 2000ms

All elements are equal; merged list contains all elements in order.

💡 Check if your code correctly handles equal values from both lists.

💡 Ensure that when values are equal, nodes from both lists are included in order.

💡 Do not skip or merge nodes with equal values incorrectly.

Why it failed: Incorrect output due to skipping or merging equal nodes incorrectly. Fix by always linking nodes even if values are equal, preserving order.

✓ Correctly merges lists with all equal elements preserving all nodes.

t2_04edge

Input{"l1":[-3,-1,0],"l2":[-2,2,3]}

Expected[-3,-2,-1,0,2,3]

⏱ Performance - must finish in 2000ms

Lists with negative and positive values merged maintaining sorted order.

💡 Check if your code handles negative values correctly.

💡 Ensure the merge logic compares values regardless of sign.

💡 Verify the merged list is sorted including negative and positive values.

Why it failed: Fails to merge negative and positive values correctly, resulting in unsorted output. Fix by comparing node values properly regardless of sign.

✓ Correctly merges lists with negative and positive values.

t3_01corner

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

Expected[1,2,3,4,5,6]

⏱ Performance - must finish in 2000ms

Merged list is sorted combining nodes from both lists.

💡 Beware of greedy mistakes that pick nodes without comparing both lists properly.

💡 Ensure you always pick the smaller node from the current heads of both lists.

💡 Fix by comparing l1.val and l2.val at each step and linking the smaller node.

Why it failed: Fails due to greedy approach picking nodes from one list without comparing both heads. Fix by always comparing and choosing smaller node.

✓ Correctly merges by comparing heads and picking smaller node each time.

t3_02corner

Input{"l1":[1,1,1],"l2":[1,1,1]}

Expected[1,1,1,1,1,1]

⏱ Performance - must finish in 2000ms

Merged list contains all nodes with equal values from both lists.

💡 Check if your code mistakenly merges nodes with equal values into one node.

💡 Remember each node is distinct even if values are equal.

💡 Fix by linking all nodes even if values are equal, preserving all nodes.

Why it failed: Incorrect output due to merging or skipping nodes with equal values. Fix by treating nodes as distinct and linking all.

✓ Correctly merges all nodes even with equal values.

t3_03corner

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

Expected[1,2,3,4,5,6]

⏱ Performance - must finish in 2000ms

Merged list is sorted interleaving nodes from both lists.

💡 Check for off-by-one errors that skip last nodes of either list.

💡 Ensure you link remaining nodes after one list is exhausted.

💡 Fix by appending the rest of the non-empty list after main merge loop.

Why it failed: Output misses last nodes due to off-by-one error or not appending remaining nodes. Fix by appending leftover nodes after main loop.

✓ Correctly merges all nodes including leftovers.

t4_01performance

Input{"l1":[0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198],"l2":[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127,129,131,133,135,137,139,141,143,145,147,149,151,153,155,157,159,161,163,165,167,169,171,173,175,177,179,181,183,185,187,189,191,193,195,197,199]}

Expectednull

⏱ Performance - must finish in 2000ms

Merging two sorted lists each with 100 nodes (total 200) must complete within 2 seconds using O(n+m) time.

💡 Use an iterative approach with O(n+m) time complexity.

💡 Avoid recursion to prevent stack overflow and extra space.

💡 Use a dummy head and two pointers to merge efficiently.

Why it failed: TLE due to using recursive approach causing stack overflow or exponential time. Fix by using iterative merge with dummy head and two pointers.

✓ Efficient O(n+m) merge confirmed by passing performance test.

Practice

1. You are given k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

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. Given the following Python code implementing the recursive reversal of a sublist, what is the output when reversing positions 2 to 3 of the list [1, 2, 3, 4]?

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last

def reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

# Build list
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(3):
    nodes[i].next = nodes[i+1]

new_head = reverseBetween(nodes[0], 2, 3)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3 2 4

B. 1 2 3 4

C. 3 2 1 4

D. 1 4 3 2

Solution

1. Step 1: Trace reverseN for n=2 starting at node with val=2

   reverseN reverses first 2 nodes starting at node 2: it recursively reverses node 3, then sets pointers to reverse links between 2 and 3.

2. Step 2: Reconnect reversed sublist to original list

   Node 1 points to reversed sublist head (node 3), and the tail of reversed sublist (node 2) points to node 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected partial reversal between positions 2 and 3 [OK]

Hint: Partial reversal swaps nodes 2 and 3 only [OK]

Common Mistakes:

• Assuming full list reversed
• Off-by-one error reversing wrong nodes
• Confusing node values with positions

4. What is the space complexity of the iterative in-place linked list addition algorithm that reuses input nodes to store the sum?

medium

A. O(max(m, n)) due to creating new nodes for sum digits

B. O(m + n) because it stores carry in a separate list

C. O(1) additional space since it modifies input lists in-place

D. O(log(max(m, n))) due to recursion stack overhead

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm modifies one input list in-place and only uses a few variables for carry and pointers.

2. Step 2: Confirm no extra list or recursion stack

   No new list nodes are created except possibly one if carry remains, which is constant extra space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place modification means constant extra space [OK]

Hint: In-place means O(1) extra space, not O(n) [OK]

Common Mistakes:

• Confusing input list size with extra space
• Assuming recursion stack space applies here
• Thinking carry requires extra list storage

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