Add Two Numbers

📋

Problem

Imagine you have two numbers represented by linked lists, where each node contains a single digit. You want to add these numbers as if you were adding them by hand, digit by digit, but the digits are stored in reverse order.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list, also in reverse order. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

The number of nodes in each linked list is in the range [1, 10^5].0 <= Node.val <= 9The input lists represent non-negative integers without leading zeros except for the number zero itself.

Edge cases: One list is longer than the other → sum correctly handles different lengthsResult has an extra digit due to carry (e.g., 5 + 5 = 10) → output list grows by one nodeOne or both lists contain only one node with 0 → output is correct zero node

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [7, 0, 12]Incorrect node value calculation; sum % 10 not applied, causing node values > 9.✅ Use node value = sum % 10 and carry = sum // 10 at each step.

Wrong: [0]Returning zero node when inputs are non-zero or ignoring carry propagation.✅ Continue traversal until both lists and carry are exhausted; do not prematurely return zero.

Wrong: [0, 0, 0]Ignoring carry propagation and not adding new node for final carry.✅ Add new node if carry > 0 after processing all nodes.

Wrong: [7, 0, 8]Stopping traversal early when second list is longer.✅ Continue traversal until both lists and carry are exhausted.

Wrong: TLE or stack overflowUsing recursive approach without tail recursion optimization on large inputs.✅ Use iterative approach with dummy head and constant extra space.

✓

Test Cases

Focus on handling lists of different lengths and carry propagation.

Watch out for off-by-one errors and ensure carry is handled after traversal.

Optimize your solution to linear time and constant space complexity.

t1_01basic

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

Expected[7,0,8]

⏱ Performance - must finish in 2000ms

342 + 465 = 807. The digits are stored in reverse order, so the output list is 7 -> 0 -> 8.

💡 Add corresponding digits from both lists and track carry.

💡 Use simultaneous traversal and a dummy head to build the result list.

💡 At each step, sum = val1 + val2 + carry; carry = sum // 10; node value = sum % 10.

Why it failed: Incorrect sum or carry handling. Fix by correctly computing carry as sum // 10 and node value as sum % 10 at each step. This is the canonical example test.

✓ Correctly handles simultaneous traversal and carry propagation.

t1_02basic

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

Expected[0]

⏱ Performance - must finish in 2000ms

0 + 0 = 0. Both lists have one node with zero, output is a single zero node.

💡 Check behavior when both inputs are minimal single-node lists.

💡 Ensure carry is initialized to zero and handled properly even if sum is zero.

💡 Return a single node with value 0 if both inputs are zero.

Why it failed: Fails to handle zero inputs correctly, possibly returning null or empty list. Fix by always returning at least one node representing zero. This is a basic zero input test.

✓ Correctly returns a single zero node for zero inputs.

t2_01edge

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

Expected[8,9,9,9,0,0,0,1]

⏱ Performance - must finish in 2000ms

9999999 + 9999 = 10009998. Carry propagates through entire list, output list grows by one node.

💡 Test carry propagation through multiple nodes of different lengths.

💡 Check that carry is added even after both lists are exhausted.

💡 Ensure the final carry creates a new node if non-zero.

Why it failed: Fails to propagate carry correctly through all nodes or misses final carry node. Fix by continuing loop while carry > 0 even if lists are exhausted. This is the carry propagation edge case.

✓ Correctly handles carry propagation and list length differences.

t2_02edge

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

Expected[1,8]

⏱ Performance - must finish in 2000ms

18 + 0 = 18. One list longer than the other, sum correctly handles different lengths.

💡 Check behavior when one list is longer than the other.

💡 Ensure traversal continues until both lists and carry are exhausted.

💡 Use zero for missing nodes in shorter list during addition.

Why it failed: Fails to handle different length lists properly, possibly stopping early. Fix by treating missing nodes as zero and continuing traversal. This is the different length edge case.

✓ Correctly sums lists of different lengths.

t2_03edge

Input{"l1":[0],"l2":[7,3]}

Expected[7,3]

⏱ Performance - must finish in 2000ms

0 + 37 = 37. One list is a single zero node, output equals the other list.

💡 Test when one list is a single zero node.

💡 Ensure zero nodes do not affect sum incorrectly.

💡 Return the other list as is if one list is zero.

Why it failed: Incorrectly adds zero node causing wrong sum or extra nodes. Fix by treating zero nodes as zero values and continuing addition. This is the single zero node edge case.

✓ Correctly handles single zero node lists.

t3_01corner

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

Expected[0,0,0,1]

⏱ Performance - must finish in 2000ms

999 + 1 = 1000. Carry must propagate creating a new node at the end.

💡 Check carry propagation when adding 1 to a number with all 9s.

💡 Ensure carry creates a new node if needed after last digits.

💡 Do not stop traversal prematurely; continue while carry > 0.

Why it failed: Fails to add new node for final carry after all nodes processed. Fix by continuing loop while carry > 0 even if lists are exhausted. This is the carry propagation corner case.

✓ Correctly handles carry propagation creating new nodes.

t3_02corner

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

Expected[7,0,8,9]

⏱ Performance - must finish in 2000ms

342 + 9465 = 9807. Handles different lengths and carry correctly.

💡 Test adding numbers where second list is longer.

💡 Ensure traversal continues until both lists and carry are exhausted.

💡 Use zero for missing nodes in shorter list during addition.

Why it failed: Fails to handle longer second list correctly, possibly ignoring extra nodes. Fix by continuing traversal until both lists and carry are exhausted. This is the different length corner case.

✓ Correctly sums lists where second list is longer.

t3_03corner

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

Expected[0,1]

⏱ Performance - must finish in 2000ms

5 + 5 = 10. Result has an extra digit due to carry.

💡 Test single node lists where sum causes carry.

💡 Ensure carry creates a new node after last digit.

💡 Do not forget to add carry node if carry > 0 after loop.

Why it failed: Fails to add extra node for carry after last digit. Fix by checking carry after loop and adding new node if needed. This is the single node carry corner case.

✓ Correctly adds extra node for carry in single node lists.

t4_01performance

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

Expected[]

⏱ Performance - must finish in 2000ms

n=100,000 digits in l1 and 1 digit in l2. Algorithm must run in O(n) time within 2 seconds.

💡 Use O(n) time simultaneous traversal with carry.

💡 Avoid recursion to prevent stack overflow on large inputs.

💡 Use iterative approach with dummy head and constant extra space.

Why it failed: TLE due to exponential or quadratic complexity. Fix by using linear time traversal with carry and no recursion. This is the performance test for O(n) complexity.

✓ Algorithm runs in linear time and passes performance constraints.

Practice

1. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. What is the space complexity of the recursive two-pointer palindrome check algorithm for a linked list of length n, and why?

medium

A. O(n) because the recursion stack stores up to n frames.

B. O(1) because no extra data structures are used.

C. O(n) because an auxiliary array of size n is created.

D. O(log n) because recursion divides the list in halves.

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm uses recursion that goes as deep as the length of the list, storing one frame per node.

2. Step 2: Understand recursion stack space

   Each recursive call adds a frame to the call stack, so total auxiliary space is O(n). No extra arrays are created.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion depth equals list length -> O(n) space [OK]

Hint: Recursion stack counts as auxiliary space [OK]

Common Mistakes:

• Assuming O(1) because no explicit arrays
• Confusing recursion with divide-and-conquer log n space
• Mistaking array approach space for recursion approach

3. Examine the following buggy code intended to remove duplicates from a sorted linked list. Which line contains the subtle bug that can cause an infinite loop or incorrect skipping of nodes?

medium

A. Line 5: current.next = current.next.next

B. Line 4: if current.val == current.next.val:

C. Line 7: current = current.next

D. Line 2: current = head

Solution

1. Step 1: Understand pointer updates

   When duplicates are found, current.next is updated to skip duplicate nodes; current pointer stays to check next node.

2. Step 2: Identify bug in pointer advancement

   If current pointer is moved unconditionally after removal, it may skip nodes or cause infinite loops. The else clause must move current only when no duplicate is removed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer advancement causes skipping or infinite loops [OK]

Hint: Only advance current when no duplicate removed [OK]

Common Mistakes:

• Advancing current pointer after removing duplicates

4. Identify the bug in the following tail-recursive reversal code snippet:

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        curr.next = prev
        next_temp = curr.next
        return helper(curr, next_temp)
    return helper(None, head)

medium

A. Line 3: Base case should check if prev is None instead of curr.

B. Line 6: The recursive call should pass next_temp as prev instead of curr.

C. Line 5: next_temp is assigned after curr.next is changed, losing original next node.

D. Line 2: The helper function should be iterative, not recursive.

Solution

1. Step 1: Analyze pointer updates

   Line 5 assigns next_temp = curr.next after curr.next is set to prev, so next_temp points to prev, not the original next node.

2. Step 2: Consequence of bug

   Because next_temp is incorrect, recursion loses the rest of the list, causing incomplete reversal or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Saving next node before pointer reversal is critical [OK]

Hint: Always save next node before changing curr.next [OK]

Common Mistakes:

• Swapping order of pointer updates
• Forgetting to set head.next to None in recursion

5. Suppose the problem is modified so that the linked list is circular (last node points back to head). Which of the following changes is necessary to correctly remove the nth node from the end in one pass?

hard

A. Use the same two-pointer approach without changes; it works as is.

B. First break the circular link to convert it into a linear list, then apply the standard algorithm.

C. Use a hash set to detect the cycle and count nodes before removal.

D. Modify the recursion to detect when the node revisits the head to stop infinite recursion.

Solution

1. Step 1: Understand circular list implications

   In a circular list, traversal never ends naturally, so counting nodes or recursion can loop infinitely.

2. Step 2: Break the cycle

   Temporarily breaking the cycle converts it to a linear list, allowing standard removal algorithms to work correctly.

3. Step 3: Restore circular link if needed

   After removal, reconnect the last node to the new head to restore circularity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Breaking cycle prevents infinite loops and enables standard logic [OK]

Hint: Circular lists require cycle breaking before linear algorithms [OK]

Common Mistakes:

• Assuming two-pointer works on circular lists
• Using recursion without cycle detection
• Using extra space unnecessarily