Add Two Numbers II (MSB First)

📋

Problem

Imagine adding two large numbers digit by digit, but the digits are stored in linked lists starting from the most significant digit. How do you add them without reversing the lists?

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in forward order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list, also in forward order. You may not modify the input lists (i.e., no reversing allowed).

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 the number 0 itself.

Edge cases: Both lists have only one node with 0 → output 0One list is significantly longer than the other → correct carry handlingSum results in an extra digit (e.g., 999 + 1 = 1000) → output list longer than inputs

</>

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, 8, 7]Ignoring carry when adding digits, resulting in missing digits or incorrect sums.✅ Add carry after summing digits and push new node accordingly; use stacks to handle addition from least significant digit.

Wrong: [9, 9, 9]Failing to add extra digit when carry remains after processing all nodes (e.g., 999 + 1).✅ Check carry after loop ends and add a new node at the front if carry > 0.

Wrong: [1, 0, 0, 0]Incorrect handling of different length lists causing missing digits or wrong carry propagation.✅ Push all digits of both lists onto stacks before addition to handle different lengths properly.

Wrong: [0]Returning empty or null for zero inputs instead of a single node with 0.✅ Return a single node with value 0 when both inputs represent zero.

Wrong: Timeout or no outputUsing inefficient reversal or recursive approaches causing TLE on large inputs.✅ Use stack-based O(n) addition without reversing input lists to meet time constraints.

✓

Test Cases

Focus on boundary inputs like single nodes and carry overflow to catch base case bugs.

Test tricky carry propagation and greedy traps to catch algorithmic mistakes.

Prepare for large inputs by ensuring your solution is O(n) time and space.

t1_01basic

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

Expected[7,8,0,7]

⏱ Performance - must finish in 2000ms

7243 + 564 = 7807, returned as linked list in forward order.

💡 Think about how to add digits starting from the least significant without reversing the lists.

💡 Use stacks to simulate reverse traversal of the linked lists.

💡 Push all digits onto stacks, then pop and add with carry, building the result from the front.

Why it failed: Incorrect sum or order indicates failure to handle carry or stack-based addition properly. Fix by using stacks to add digits from least significant to most significant.

✓ Correctly adds two numbers represented by linked lists in forward order using stack-based addition.

t1_02basic

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

Expected[1,9,9,9]

⏱ Performance - must finish in 2000ms

1000 + 999 = 1999, returned as linked list in forward order.

💡 Check how carry propagates when one list is longer than the other.

💡 Ensure you handle different lengths by pushing all digits onto stacks before addition.

💡 After adding all digits, if carry remains, add a new node at the front.

Why it failed: Failing to handle different lengths or leftover carry leads to wrong output. Fix by pushing all digits onto stacks and adding carry after processing all digits.

✓ Handles different lengths and carry correctly, producing the right sum.

t2_01edge

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

Expected[0]

⏱ Performance - must finish in 2000ms

Both lists represent zero; sum is zero.

💡 Consider the smallest input size with minimal values.

💡 Check if your code handles single-node lists correctly.

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

Why it failed: Returning empty list or multiple nodes for zero input is incorrect. Fix by returning a single node with value 0 when both inputs are zero.

✓ Correctly returns zero for both single-node zero inputs.

t2_02edge

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

Expected[1,0,0,0]

⏱ Performance - must finish in 2000ms

999 + 1 = 1000, sum has more digits than inputs.

💡 Test cases where sum results in an extra digit.

💡 Ensure carry is added as a new node at the front if it remains after processing all digits.

💡 Use a dummy head or prepend nodes to handle carry overflow.

Why it failed: Missing the extra digit from carry leads to shorter output. Fix by adding a new node at the front if carry remains after addition.

✓ Correctly handles carry overflow producing longer output list.

t2_03edge

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

Expected[1,0]

⏱ Performance - must finish in 2000ms

Leading zeros in input lists (not allowed by constraints) but sum 1 + 9 = 10, output should be [1,0].

💡 Check if your code can handle leading zeros gracefully.

💡 Leading zeros should not affect the sum calculation.

💡 Strip leading zeros from the result if any appear.

Why it failed: Failing to handle leading zeros may cause incorrect output length or values. Fix by ignoring leading zeros in input and trimming leading zeros in output if needed.

✓ Handles leading zeros in input and produces correct sum without leading zeros.

t3_01corner

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

Expected[1,9,9,8]

⏱ Performance - must finish in 2000ms

999 + 999 = 1998, tests carry propagation through all digits.

💡 Check if carry is propagated correctly through all digits.

💡 Avoid off-by-one errors in carry handling.

💡 Ensure carry is added as a new node if it remains after processing all digits.

Why it failed: Incorrect carry propagation leads to wrong sum digits. Fix by correctly updating carry and adding new node if carry remains after loop.

✓ Correctly propagates carry through all digits producing accurate sum.

t3_02corner

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

Expected[1,1,1,0]

⏱ Performance - must finish in 2000ms

123 + 987 = 1110, tests correct addition and carry with no reversal allowed.

💡 Beware of greedy approaches that add digits without carry.

💡 Use stacks to simulate reverse addition correctly.

💡 Add carry after each digit sum and prepend nodes accordingly.

Why it failed: Greedy addition without carry leads to wrong sum. Fix by using stack-based addition with carry propagation.

✓ Correctly adds digits with carry producing the right sum.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

10000 + 9 = 10009, tests handling of long list with small list and carry.

💡 Check handling of different length lists with carry.

💡 Ensure no reversal of input lists is done.

💡 Use stacks to add digits from least significant to most significant.

Why it failed: Confusing 0/1 knapsack style logic or reversing input leads to wrong output. Fix by using stack-based addition without reversing input lists.

✓ Handles different lengths and carry correctly without reversing inputs.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) stack-based addition must complete within 2 seconds.

💡 Use O(n) time and O(n) space stack-based addition.

💡 Avoid reversing linked lists to meet time constraints.

💡 Efficiently handle carry and node creation.

Why it failed: Brute force or reversing input lists causes TLE due to O(n^2) or higher complexity. Fix by using stack-based O(n) addition.

✓ Solution runs in O(n) time confirming efficient stack-based addition.

Practice

1. Consider the following code that deletes a node from a singly linked list given only access to that node. What is the output after deleting the node with value 5?

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

def deleteNode(node):
    node.val = node.next.val
    node.next = node.next.next

n4 = ListNode(9)
n3 = ListNode(1, n4)
n2 = ListNode(5, n3)
n1 = ListNode(4, n2)

deleteNode(n2)

curr = n1
while curr:
    print(curr.val, end=' -> ' if curr.next else '\n')
    curr = curr.next

easy

A. 4 -> 9

B. 4 -> 1 -> 1 -> 9

C. 4 -> 1 -> 9

D. 4 -> 5 -> 1 -> 9

Solution

1. Step 1: Trace deleteNode on node with value 5

   Copy next node's value (1) into current node (5), so node.val becomes 1. Then update node.next to skip next node, pointing to node with value 9.

2. Step 2: Print the list after deletion

   List is now 4 -> 1 -> 9, as the original node with 5 is replaced by 1 and next points to 9.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Node 5 replaced by 1, next pointer updated correctly [OK]

Hint: Copy next node's value and skip next node [OK]

Common Mistakes:

• Forgetting to update next pointer, causing duplicates
• Printing original list without changes
• Confusing node values after deletion

2. Consider the following code snippet implementing the two-pointer approach to find the intersection of two linked lists. Given the lists: listA: 1 -> 2 -> 3 -> 4 -> 5 listB: 9 -> 4 -> 5 where nodes with values 4 and 5 are shared (intersection starts at node with value 4). What is the value returned by the function?

easy

A. 3

B. 4

C. 5

D. No intersection

Solution

1. Step 1: Trace pointers through lists

   pA starts at 1, pB at 9. They advance until pA reaches 4, pB reaches 4 (intersection node). Since nodes are shared, pA is pB at node with value 4.

2. Step 2: Confirm return value

   The function returns the intersection node, which has value 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Intersection node value is 4 as expected [OK]

Hint: Pointers meet at shared node 4 [OK]

Common Mistakes:

• Returning node value instead of node reference
• Confusing next pointers
• Off-by-one in pointer switching

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.

Solution

1. Step 1: Identify problem with head duplicates

   Without a dummy node, if duplicates appear at the head, prev is None and cannot link to the new head after removal.

2. Step 2: Analyze code behavior

   Line 3 initializes prev to None instead of a dummy node, so when duplicates at the head are removed, the head pointer is not updated correctly, causing incorrect output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dummy node needed to handle head duplicates [OK]

Hint: Always use dummy node to handle head duplicates [OK]

Common Mistakes:

• Not using dummy head
• Incorrect prev updates
• Skipping null checks

4. Suppose you want to merge two sorted linked lists where nodes can be reused multiple times (i.e., each node can appear multiple times in the merged list). Which modification to the in-place merge algorithm correctly handles this scenario?

hard

A. Create a new list and copy nodes from both lists, allowing duplicates by reusing values but not nodes.

B. Use a recursive merge that creates new nodes for each occurrence to avoid pointer conflicts.

C. Modify the algorithm to allow nodes to be linked multiple times by not advancing pointers after attaching nodes.

D. Use the same in-place merge but reset pointers to the start of lists after each merge step.

Solution

1. Step 1: Understand node reuse constraints

   Reusing nodes multiple times in a linked list is impossible without creating new nodes because each node can only have one next pointer.

2. Step 2: Identify correct approach

   To allow duplicates, the algorithm must create new nodes for each occurrence, which recursion can do naturally by creating new nodes on each call.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive merge with new nodes handles duplicates safely [OK]

Hint: Nodes cannot be reused multiple times without duplication [OK]

Common Mistakes:

• Trying to reuse nodes by resetting pointers causes cycles
• Assuming in-place merge can handle duplicates without new nodes
• Not realizing linked list nodes have single next pointer

5. Suppose the linked list rotation problem is modified so that k can be negative, indicating rotation to the left by |k| places. Which modification to the optimal algorithm correctly handles negative k values?

hard

A. Ignore negative k and return the original list without rotation.

B. Convert negative k to positive by k = abs(k) and rotate right as usual.

C. Adjust k by k = (k % length + length) % length to normalize negative rotations to equivalent right rotations.

D. Reverse the list first, then apply the original rotation algorithm with positive k.

Solution

1. Step 1: Understand negative rotation meaning

   Negative k means rotate left by |k|, which is equivalent to rotating right by length - |k|.

2. Step 2: Normalize k to positive equivalent

   Using k = (k % length + length) % length converts negative k to correct positive rotation count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Normalization handles negative rotations correctly [OK]

Hint: Normalize k with modulo to handle negatives [OK]

Common Mistakes:

• Taking absolute value loses rotation direction
• Ignoring negative k leads to wrong output
• Reversing list unnecessarily complicates solution