Add Two Numbers

▶

Steps

setup

Initialize pointers and carry

Set 'head' to point to the start of l1, initialize 'carry' to 0, and 'prev' to None before starting the addition loop.

💡 This sets up the variables needed to traverse and modify the lists in-place.

Line:

head = l1
carry = 0
prev = None

💡 We will reuse l1 nodes to store the result, so keeping 'head' preserves the result list start.

fill_cells

Add first digits and carry

Add values of l1 (2) and l2 (5) plus carry (0). Total is 7, carry becomes 0. Update l1 node's value to 7.

💡 This is the first digit sum, showing how nodes are updated in-place.

Line:

val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
l1.val = total % 10

💡 The sum digit fits in one node without carry, so no new node needed.

traverse

Advance pointers after first addition

Move l1 and l2 pointers to their next nodes to prepare for the next digit addition.

💡 Advancing pointers is essential to process all digits sequentially.

Line:

prev = l1
l1 = l1.next
if l2:
    l2 = l2.next

💡 Pointers track current nodes to add; moving them forward progresses the addition.

fill_cells

Add second digits and carry

Add values of l1 (4) and l2 (6) plus carry (0). Total is 10, so carry becomes 1 and l1 node value is updated to 0.

💡 This step shows how carry is generated when sum exceeds 9.

Line:

val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
l1.val = total % 10

💡 Carry must be remembered for the next digit addition.

traverse

Advance pointers after second addition

Move l1 and l2 pointers to their next nodes to prepare for the last digit addition.

💡 Moving pointers forward is necessary to process all digits.

Line:

prev = l1
l1 = l1.next
if l2:
    l2 = l2.next

💡 Pointers now point to the last nodes of each list.

fill_cells

Add third digits and carry

Add values of l1 (3) and l2 (4) plus carry (1). Total is 8, carry becomes 0, update l1 node value to 8.

💡 Final digit addition with carry from previous step.

Line:

val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
l1.val = total % 10

💡 Carry is cleared after this addition, no new node needed.

traverse

Advance pointers after third addition

Move l1 and l2 pointers to next nodes, both become null indicating end of lists.

💡 End of both lists reached, check if carry remains.

Line:

prev = l1
l1 = l1.next if l1 else None
if l2:
    l2 = l2.next

💡 No more digits to add, but carry must be checked.

insert

Check for leftover carry

Since carry is 0, no new node is appended. The result list is complete.

💡 If carry was nonzero, a new node would be created here.

Line:

if carry:
    prev.next = ListNode(carry)
    prev = prev.next

💡 Carry determines if the result list needs to grow beyond input length.

reconstruct

Return the head of the result list

Return the head pointer which points to the modified l1 list representing the sum.

💡 Returning head gives access to the full sum list for output or further use.

Line:

return head

💡 The result is stored in-place in l1, no extra list created.

reconstruct

Final result visualization

The final linked list represents the sum 807 as [7 -> 0 -> 8]. This is the output of the algorithm.

💡 Seeing the final list confirms the correctness of the in-place addition.

💡 The sum digits are stored in reverse order, matching the problem requirement.

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

def addTwoNumbersInPlace(l1, l2):
    head = l1  # STEP 1: Initialize head
    carry = 0  # STEP 1: Initialize carry
    prev = None  # STEP 1: Initialize prev
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0  # STEP 2,4,6: Get l1 value
        val2 = l2.val if l2 else 0  # STEP 2,4,6: Get l2 value
        total = val1 + val2 + carry  # STEP 2,4,6: Calculate sum
        carry = total // 10  # STEP 2,4,6: Update carry
        if l1:
            l1.val = total % 10  # STEP 2,4,6: Update l1 node
            prev = l1  # STEP 3,5,7: Update prev
            l1 = l1.next  # STEP 3,5,7: Advance l1
        else:
            prev.next = ListNode(total % 10)  # STEP 8: Append new node if l1 ended
            prev = prev.next  # STEP 8: Update prev
        if l2:
            l2 = l2.next  # STEP 3,5,7: Advance l2
    return head  # STEP 9: Return result

📊

Add Two Numbers - Watch the Algorithm Execute, Step by Step

Watching each addition and pointer movement helps you understand how the algorithm reuses nodes and manages carry without extra space.

setup

2

→

4

→

3

→

5

→

6

→

4

fill_cells

7

→

4

→

3

→

5

→

6

→

4

Result: [7]

traverse

7

→

4

→

3

→

5

→

6

→

4

Result: [7]

fill_cells

7

→

0

→

3

→

5

→

6

→

4

Result: [7, 0]

traverse

7

→

0

→

3

→

5

→

6

→

4

Result: [7, 0]

fill_cells

7

→

0

→

8

→

5

→

6

→

4

Result: [7, 0, 8]

traverse

7

→

0

→

8

→

5

→

6

→

4

Result: [7, 0, 8]

insert

7

→

0

→

8

Result: [7, 0, 8]

reconstruct

7

→

0

→

8

Result: [7, 0, 8]

reconstruct

7

→

0

→

8

Result: [7, 0, 8]

Key Takeaways

✓ The algorithm modifies the first list in-place to store the sum, avoiding extra space.

This is hard to see from code alone because the reuse of nodes is implicit; visualization shows node value changes clearly.

✓ Carry is propagated through the addition and may cause new nodes to be appended if needed.

Visualizing carry and when new nodes are created clarifies how the algorithm handles sums exceeding 9.

✓ Pointer advancement and tracking 'prev' is crucial to correctly link new nodes when l1 ends before l2 or carry remains.

Seeing pointer movements step-by-step helps understand how the list is extended dynamically.

Practice

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

2. Consider the following Python code implementing the optimal merge K sorted lists approach using a min-heap. Given the input lists: [1->4->5], [1->3->4], [2->6], what is the value of current.next.val after the third iteration of the while loop?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Initialize heap with heads: 1,1,2

   Heap order: [1,1,2]

2. Step 2: Iterations of while loop

   1st pop: smallest=1 (from first list), push 4; 2nd pop: smallest=1 (from second list), push 3; 3rd pop: smallest=2 (from third list), push 6. After 3rd iteration, current.next.val = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Third extracted node value is 2 [OK]

Hint: Track heap pops and pushed next nodes carefully [OK]

Common Mistakes:

• Off-by-one iteration counting
• Confusing which node is popped
• Forgetting to push next nodes

3. What is the time complexity of deleting a node in a singly linked list given only access to that node (no head pointer), using the optimal in-place approach that copies the next node's data and deletes the next node?

medium

A. O(n), because you need to traverse the list to find the node

B. O(1), because the operation only involves copying data and pointer updates

C. O(n), because you must recursively copy data from subsequent nodes

D. O(log n), because the deletion involves dividing the list

Solution

1. Step 1: Identify operations performed

   The algorithm copies the next node's value into the current node and updates the next pointer to skip the next node.

2. Step 2: Analyze time complexity

   These operations are constant time, no traversal or recursion is needed.

3. Step 3: Consider the initial access to the node

   However, if only the node to delete is given, no traversal is needed. But if only the value is given and node must be found, traversal is needed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Copy and pointer update are O(1) operations [OK]

Hint: No traversal needed; only local pointer updates [OK]

Common Mistakes:

• Assuming traversal from head is needed, making it O(n)
• Confusing recursion with iterative approach
• Thinking deletion involves multiple node copies

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

5. What is the time complexity of the optimal linked list rotation algorithm that uses two pointers and connects the tail to the head to form a circular list before breaking it at the new tail?

medium

A. O(n), where n is the length of the list

B. O(k * n), where k is the rotation count and n is the list length

C. O(n + k), where n is list length and k is rotation count

D. O(n^2), due to nested pointer traversals

Solution

1. Step 1: Identify main operations

   Traversing the list once to find length and tail is O(n).

2. Step 2: Pointer movements

   Moving fast pointer k steps and slow pointer until fast reaches tail is at most O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations combined are linear in n [OK]

Hint: Length calculation + single pass pointer moves -> O(n) [OK]

Common Mistakes:

• Assuming O(k*n) due to repeated rotations
• Confusing k with n in complexity
• Thinking nested loops cause O(n^2)