Add Two Numbers II (MSB First)

▶

Steps

setup

Calculate length of l1

Traverse l1 to count its length. l1 has nodes [7,2,4,3], so length is 4.

💡 Knowing the length helps determine if padding is needed to align the lists.

Line:

len1 = getLength(l1)

💡 Lengths are needed to align the lists for digit-wise addition.

setup

Calculate length of l2

Traverse l2 to count its length. l2 has nodes [5,6,4], so length is 3.

💡 Comparing lengths tells us which list to pad.

Line:

len2 = getLength(l2)

💡 l2 is shorter, so it will be padded with zeros.

expand

Pad l2 with one zero node

Since l2 is shorter by 1, add a zero node at the front: l2 becomes [0,5,6,4].

💡 Padding aligns the lists so corresponding nodes represent the same digit place.

Line:

l2 = padList(l2, len1 - len2)

💡 Both lists now have length 4, enabling digit-wise addition.

traverse

Begin recursive addition at head nodes

Call addListsHelper on l1 and padded l2 heads: nodes with values 7 and 0.

💡 Recursion will go to the end of the lists before adding digits.

Line:

next_node, carry = addListsHelper(l1.next, l2.next)

💡 Recursion depth increases, postponing addition until base case.

traverse

Recursive call: add nodes with values 2 and 5

Next recursion level adds nodes with values 2 (l1) and 5 (l2).

💡 Each recursive call moves one node forward in both lists.

Line:

next_node, carry = addListsHelper(l1.next, l2.next)

💡 Stack grows deeper until reaching the last nodes.

traverse

Recursive call: add nodes with values 4 and 6

Next recursion level adds nodes with values 4 (l1) and 6 (l2).

💡 Recursion continues until the last nodes are reached.

Line:

next_node, carry = addListsHelper(l1.next, l2.next)

💡 The recursion stack now holds nodes for positions 0 to 2.

traverse

Recursive call: add nodes with values 3 and 4 (last nodes)

Last recursion level adds nodes with values 3 (l1) and 4 (l2).

💡 Base case is reached after this call when both next nodes are None.

Line:

if not l1 and not l2:
    return (None, 0)

💡 Recursion will now start returning and summing digits.

traverse

Base case reached: both nodes None

Reached end of both lists; return (None, 0) to start addition.

💡 This triggers unwinding of recursion and digit addition.

Line:

if not l1 and not l2:
    return (None, 0)

💡 Base case returns zero carry and no node.

insert

Add last nodes: 3 + 4 + carry 0 = 7

Create node with value 7 (3+4+0), carry 0, link to None.

💡 Sum digit and carry form new node; carry propagates up.

Line:

total = l1.val + l2.val + carry
node = ListNode(total % 10)
node.next = next_node
return (node, total // 10)

💡 Digit sum mod 10 forms node value; carry is total // 10.

insert

Add nodes: 4 + 6 + carry 0 = 10

Create node with value 0 (10 % 10), carry 1 (10 // 10), link to node 7.

💡 Carry 1 will affect next higher digit addition.

Line:

total = l1.val + l2.val + carry
node = ListNode(total % 10)
node.next = next_node
return (node, total // 10)

💡 Carry is propagated correctly to higher digit.

insert

Add nodes: 2 + 5 + carry 1 = 8

Create node with value 8 (8 % 10), carry 0 (8 // 10), link to node 0.

💡 Carry cleared, addition continues normally.

Line:

total = l1.val + l2.val + carry
node = ListNode(total % 10)
node.next = next_node
return (node, total // 10)

💡 Carry can be zero, simplifying next steps.

insert

Add nodes: 7 + 0 + carry 0 = 7

Create node with value 7 (7 % 10), carry 0, link to node 8.

💡 Final addition at head nodes completes the sum list.

Line:

total = l1.val + l2.val + carry
node = ListNode(total % 10)
node.next = next_node
return (node, total // 10)

💡 No carry remains, so no new head node needed.

insert

Check for leftover carry and finalize

Carry is 0, so no new head node is added. Return the head of the summed list.

💡 Final carry check ensures correct result length.

Line:

if carry:
    head = ListNode(carry, head)

💡 Carry can extend the list length by one if nonzero.

reconstruct

Final summed linked list ready

The resulting linked list represents the sum: [7,8,0,7].

💡 This is the final output of the algorithm.

Line:

return head

💡 The sum is correctly represented in forward order.

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

def getLength(head):
    length = 0
    while head:
        length += 1  # STEP 1 & 2
        head = head.next
    return length

def padList(head, padding):
    for _ in range(padding):
        head = ListNode(0, head)  # STEP 3
    return head

def addListsHelper(l1, l2):
    if not l1 and not l2:
        return (None, 0)  # STEP 8
    next_node, carry = addListsHelper(l1.next, l2.next)  # STEP 4-7
    total = l1.val + l2.val + carry  # STEP 9-12
    node = ListNode(total % 10)
    node.next = next_node
    return (node, total // 10)

def addTwoNumbers(l1, l2):
    len1 = getLength(l1)  # STEP 1
    len2 = getLength(l2)  # STEP 2
    if len1 < len2:
        l1 = padList(l1, len2 - len1)
    else:
        l2 = padList(l2, len1 - len2)  # STEP 3
    head, carry = addListsHelper(l1, l2)  # STEP 4-12
    if carry:
        head = ListNode(carry, head)  # STEP 13
    return head  # STEP 14

📊

Add Two Numbers II (MSB First) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how recursion and stack operations simulate addition from least significant digit to most significant digit without reversing the lists.

no_opElement[0]: 7

Stack (top→bottom)

empty

no_opElement[0]: 5

Stack (top→bottom)

empty

pushElement[0]: 0

Stack (top→bottom)

empty

↑ pushed: 0

pushElement[0]: 7

Stack (top→bottom)

7

↑ pushed: 7

pushElement[1]: 2

Stack (top→bottom)

2

7

↑ pushed: 2

pushElement[2]: 4

Stack (top→bottom)

4

2

7

↑ pushed: 4

pushElement[3]: 3

Stack (top→bottom)

3

4

2

7

↑ pushed: 3

no_op

Stack (top→bottom)

3

4

2

7

popElement[3]: 3

Stack (top→bottom)

7

4

2

7

↓ popped: [3]

Contributes: 7

popElement[2]: 4

Stack (top→bottom)

7

0

2

7

↓ popped: [4]

Contributes: 0

popElement[1]: 2

Stack (top→bottom)

7

0

8

7

↓ popped: [2]

Contributes: 8

popElement[0]: 7

Stack (top→bottom)

7

0

8

7

↓ popped: [7]

Contributes: 7

no_opElement[0]: 7

Stack (top→bottom)

7

0

8

7

no_opElement[0]: 7

Stack (top→bottom)

7

0

8

7

Key Takeaways

✓ Recursion simulates addition from least significant digit to most significant digit without reversing the lists.

This insight is hard to see from code alone because recursion hides the order of operations.

✓ Padding the shorter list with zeros aligns digits for correct addition.

Visualizing padding clarifies why lists must be equal length before addition.

✓ Carry propagation is handled naturally by returning carry up the recursion stack.

Seeing carry flow back up the stack helps understand how addition carries are managed.

Practice

1. You are given a pointer to a node in a singly linked list, but you do not have access to the head of the list. You need to delete this node from the list in-place. Which approach guarantees an optimal solution for this problem?

easy

A. Copy the data from the next node into the current node, then delete the next node.

B. Mark the node as deleted and skip it during traversal without modifying pointers.

C. Use a recursive function to traverse and delete the node starting from the given node.

D. Traverse from the head node to find the previous node and update its next pointer.

Solution

1. Step 1: Understand the problem constraints

   We only have access to the node to delete, not the head, so traversing from head is impossible.

2. Step 2: Identify the approach that works without head

   Copying the next node's data into the current node and deleting the next node effectively removes the current node's value and maintains list integrity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Deleting without head requires copying next node's data [OK]

Hint: Deleting without head requires copying next node's data [OK]

Common Mistakes:

• Trying to delete by setting node to null without updating pointers
• Attempting to traverse from head when head is not given
• Marking node deleted without pointer updates

2. Given the following recursive code to remove duplicates from a sorted linked list, what is the final list returned when the input list is [1, 2, 2, 3]?

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

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

easy

A. [1, 2, 3]

B. [2, 3]

C. [1, 3]

D. [1]

Solution

1. Step 1: Trace initial call with head=1

   1 != 2, so recurse on deleteDuplicates(2 -> 2 -> 3).

2. Step 2: Trace call with head=2

   2 == 2, remove all nodes with val=2 by advancing head until head.val != 2, resulting in head=3. Recurse on deleteDuplicates(3).

3. Step 3: Trace call with head=3

   Only one node, return head as is.

4. Step 4: Reconstruct list

   From step 1, head=1, head.next = result from step 3 (3), so final list is [1, 3].

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Duplicates 2 removed completely, 1 and 3 remain [OK]

Hint: Duplicates removed recursively, only distinct nodes remain [OK]

Common Mistakes:

• Leaving one duplicate node
• Not skipping all duplicates in while loop
• Incorrectly linking nodes after recursion

3. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Iteratively reverse nodes in groups of k using a helper function, with a dummy node to manage connections.

B. Apply dynamic programming to store reversed sublists and merge them after processing all nodes.

C. Use a greedy approach that reverses nodes whenever possible without checking group size, then reconnects the list.

D. Recursively reverse the entire list and then split it into k-sized groups.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing nodes in groups of k only if the group size is exactly k; partial groups remain unchanged.

2. Step 2: Identify the approach that respects group boundaries and performs in-place reversal

   The iterative approach with a helper function and dummy node efficiently reverses each k-group and reconnects the list in O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterative helper with dummy node handles group boundaries correctly [OK]

Hint: Dummy node + helper function ensures clean in-place reversal [OK]

Common Mistakes:

• Greedy reversal without checking group size causes partial reversals
• Recursion causes stack overflow on large lists
• Dynamic programming is unnecessary overhead here

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