How to Solve: Add Two Numbers Represented by Linked Lists

How to Solve: Add Two Numbers Represented by Linked Lists

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle edge cases, pointer manipulation, and clean code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Singly Linked List Basics (traversal, dummy nodes, pointer updates). 2. Carry Propagation (how addition overflow works in base-10). 3. Time/Space Complexity (O(n) time, O(1) or O(n) space trade-offs).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every linked-list addition problem.)

1. Initialize a dummy node to simplify head handling.
2. Set a current pointer to build the result list.
3. Initialize carry = 0 to track overflow.
4. Loop while either list has nodes or carry exists:
5. Extract digits: val1 = l1.val if l1 else 0, val2 = l2.val if l2 else 0.
6. Compute sum: sum_val = val1 + val2 + carry.
7. Update carry: carry = sum_val // 10.
8. Create new node: current.next = ListNode(sum_val % 10).
9. Move pointers: l1 = l1.next if l1 else None, l2 = l2.next if l2 else None, current = current.next.
10. Return dummy.next (the actual head of the result).
11. Test edge cases:
12. One list is empty.
13. Both lists are empty.
14. Carry remains after traversal (e.g., 999 + 1 = 1000).

? WORKED EXAMPLES

Example 1 – Basic: Add Two Numbers (LeetCode 2)

Problem: Two non-empty linked lists represent non-negative integers in reverse order. Add them and return the sum as a linked list. Input: l1 = [2,4,3], l2 = [5,6,4] (represents 342 + 465 = 807) Output: [7,0,8]

Thought Process

1. Dummy node avoids null checks for the head.
2. Carry propagates through the sum.
3. Early termination handles lists of unequal length.

Code (Python)

class ListNode:

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

        self.val = val

        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:

    dummy = ListNode(0)

    current = dummy

    carry = 0


    while l1 or l2 or carry:

        val1 = l1.val if l1 else 0

        val2 = l2.val if l2 else 0

        sum_val = val1 + val2 + carry

        carry = sum_val // 10

        current.next = ListNode(sum_val % 10)

        current = current.next

        l1 = l1.next if l1 else None

        l2 = l2.next if l2 else None


    return dummy.next

Complexity

• Time: O(max(m, n)) (traverse both lists once).
• Space: O(max(m, n)) (new list for result).

Why This Works

• Dummy node simplifies edge cases (e.g., empty lists).
• Carry handling ensures correct digit propagation.
• Early termination (while l1 or l2 or carry) covers all cases.

Example 2 – Medium: Add Two Numbers II (LeetCode 445)

Problem: Numbers are stored in forward order (e.g., [7,2,4,3] = 7243). Return the sum in the same order. Input: l1 = [7,2,4,3], l2 = [5,6,4] (7243 + 564 = 7807) Output: [7,8,0,7]

Twist

• Cannot reverse the input lists (interviewer constraint).
• Must handle carry backwards (from least significant digit to most).

Approach

1. Use stacks to reverse the digits (LIFO order).
2. Pop digits from stacks, compute sum, and build the result in reverse.
3. Reverse the result at the end.

Code (Python)

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:

    stack1, stack2 = [], []


    # Push all digits to stacks

    while l1:

        stack1.append(l1.val)

        l1 = l1.next

    while l2:

        stack2.append(l2.val)

        l2 = l2.next


    carry = 0

    result = None


    while stack1 or stack2 or carry:

        val1 = stack1.pop() if stack1 else 0

        val2 = stack2.pop() if stack2 else 0

        sum_val = val1 + val2 + carry

        carry = sum_val // 10

        # Prepend new node (reverse order)

        new_node = ListNode(sum_val % 10)

        new_node.next = result

        result = new_node


    return result

Complexity

• Time: O(m + n) (traverse lists twice: once for stacks, once for sum).
• Space: O(m + n) (stacks + result list).

Why This Works

• Stacks reverse the digits without modifying input lists.
• Prepend nodes to build the result in forward order.

Example 3 – Hard/Follow-Up: Add Two Numbers with In-Place Modification

Problem: Modify one of the input lists to store the result (no extra space). Constraint: Cannot create new nodes; must reuse existing ones.

Approach

1. Reverse both lists to process digits from least significant.
2. Traverse and update one list in-place.
3. Reverse the result back to original order.

Code (Python)

def reverseList(head: ListNode) -> ListNode:

    prev = None

    while head:

        next_node = head.next

        head.next = prev

        prev = head

        head = next_node

    return prev

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:

    # Reverse both lists

    l1 = reverseList(l1)

    l2 = reverseList(l2)


    dummy = ListNode(0)

    current = dummy

    carry = 0


    while l1 or l2 or carry:

        val1 = l1.val if l1 else 0

        val2 = l2.val if l2 else 0

        sum_val = val1 + val2 + carry

        carry = sum_val // 10

        # Reuse l1's nodes (or l2's)

        if l1:

            l1.val = sum_val % 10

            current.next = l1

            l1 = l1.next

        else:

            current.next = ListNode(sum_val % 10)

        current = current.next


    # Reverse the result back

    return reverseList(dummy.next)

Complexity

• Time: O(m + n) (reverse + traverse + reverse).
• Space: O(1) (no extra space except pointers).

Why This Works

• Reversing lists allows in-place updates.
• Reusing nodes avoids allocation (interviewer may ask for this).

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second cheat sheet for linked-list addition problems:

1. Start with a dummy node—it’s your best friend for avoiding null checks.
2. Loop until both lists and carry are exhausted—never assume equal lengths.
3. Handle carry at every step—it’s the silent killer of edge cases.
4. For forward-order numbers, use stacks or reverse the lists.
5. If asked for O(1) space, reverse the lists, update in-place, and reverse back.

Test your code with: - Empty lists. - Carry at the end (e.g., 999 + 1). - One list longer than the other.

Now go crush that interview!"

? Final Notes

• Practice: Implement all 3 examples from scratch.
• Whiteboard: Draw the linked lists and carry propagation.
• Edge Cases: Always test with [] + [1], [9,9] + [1], and [0] + [0].

This framework is directly usable in any FAANG interview. Good luck! ?