Add Two Numbers

🎯

Add Two Numbers

mediumLINKED_LISTAmazonMicrosoftGoogle

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.

💡 This problem is a classic linked list manipulation task that combines understanding of linked list traversal with elementary addition and carry handling. Beginners often struggle because it requires simultaneous traversal of two lists, managing carry, and building a new list without losing track of nodes.

📋

Problem Statement

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.

💡

Example

Input"l1 = [2,4,3], l2 = [5,6,4]"

Output[7,0,8]

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

• One list is longer than the other → sum correctly handles different lengths
• Result has an extra digit due to carry (e.g., 5 + 5 = 10) → output list grows by one node
• One or both lists contain only one node with 0 → output is correct zero node
• Lists with all nodes as 9 → carry propagates through entire list

⚠️

Common Mistakes

Not handling carry after both lists are exhausted

Missing the last carry digit, resulting in incorrect sum

✅ Ensure loop continues while carry is non-zero

Not handling different list lengths properly

Null pointer exceptions or incorrect sums when one list is shorter

✅ Use 0 for missing nodes when one list is shorter

Losing reference to the head of the result list

Unable to return the correct result or runtime errors

✅ Use a dummy head node to simplify list construction

Using recursion without base case or improper base case

Stack overflow or infinite recursion

✅ Define clear base case when both lists and carry are empty/zero

Modifying input lists without permission or care

Unexpected side effects or corrupted input data

✅ Clarify if in-place modification is allowed; otherwise create new nodes

🧠

Brute Force (Simultaneous Traversal with Carry)

💡 This approach is the foundational way to solve the problem by simulating the addition digit by digit, just like elementary school addition. It helps beginners understand the problem deeply before optimizing.

Intuition

Traverse both linked lists simultaneously, add corresponding digits along with any carry from the previous addition, create new nodes for the result, and handle leftover carry at the end.

Algorithm

1. Initialize a dummy head node to simplify result list construction.
2. Initialize a carry variable to 0.
3. Traverse both lists simultaneously until both are exhausted and carry is zero.
4. At each step, sum the digits from both lists and the carry, create a new node with the digit part of the sum, update carry, and move pointers forward.

💡 The challenge is to keep track of carry and handle lists of different lengths while building the result list without losing references.

</>

Code

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

def addTwoNumbers(l1, 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
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    # Helper to create linked list from list
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for num in arr:
            cur.next = ListNode(num)
            cur = cur.next
        return dummy.next

    l1 = create_list([2,4,3])
    l2 = create_list([5,6,4])
    result = addTwoNumbers(l1, l2)
    # Print result
    while result:
        print(result.val, end=' ')
        result = result.next
    print()

Line Notes

dummy = ListNode(0)Create a dummy node to simplify edge cases and result list construction

carry = 0Initialize carry to handle sums greater than 9

while l1 or l2 or carry:Continue until both lists are exhausted and no carry remains

val1 = l1.val if l1 else 0Use 0 if l1 is exhausted to handle different length lists

total = val1 + val2 + carrySum current digits and carry to get total for this digit

carry = total // 10Update carry for next iteration

current.next = ListNode(total % 10)Create new node with digit part of sum

if l1: l1 = l1.nextAdvance l1 pointer if possible

return dummy.nextReturn head of the resulting linked list, skipping dummy

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int total = val1 + val2 + carry;
            carry = total / 10;
            current.next = new ListNode(total % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{2,4,3});
        ListNode l2 = createList(new int[]{5,6,4});
        ListNode result = sol.addTwoNumbers(l1, l2);
        printList(result);
    }

    private static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int num : arr) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node simplifies list construction and edge cases

int carry = 0;Carry initialized to zero for addition

while (l1 != null || l2 != null || carry != 0)Loop until both lists and carry are fully processed

int val1 = (l1 != null) ? l1.val : 0;Use 0 if l1 is exhausted to handle unequal lengths

carry = total / 10;Calculate carry for next digit addition

current.next = new ListNode(total % 10);Create new node for current digit of sum

if (l1 != null) l1 = l1.next;Advance l1 pointer if possible

return dummy.next;Return head of the result list, skipping dummy

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            int total = val1 + val2 + carry;
            carry = total / 10;
            current->next = new ListNode(total % 10);
            current = current->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        return dummy.next;
    }
};

// Helper functions for testing
ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* node) {
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    int arr1[] = {2,4,3};
    int arr2[] = {5,6,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    ListNode* result = sol.addTwoNumbers(l1, l2);
    printList(result);
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node to simplify result list construction

int carry = 0;Initialize carry for addition

while (l1 || l2 || carry)Loop until both lists and carry are fully processed

int val1 = l1 ? l1->val : 0;Use 0 if l1 is exhausted to handle different lengths

carry = total / 10;Calculate carry for next iteration

current->next = new ListNode(total % 10);Create new node for current digit

if (l1) l1 = l1->next;Advance l1 pointer if possible

return dummy.next;Return head of the result list, skipping dummy

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function addTwoNumbers(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;
    while (l1 !== null || l2 !== null || carry !== 0) {
        let val1 = l1 !== null ? l1.val : 0;
        let val2 = l2 !== null ? l2.val : 0;
        let total = val1 + val2 + carry;
        carry = Math.floor(total / 10);
        current.next = new ListNode(total % 10);
        current = current.next;
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
    return dummy.next;
}

// Driver code
function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let num of arr) {
        cur.next = new ListNode(num);
        cur = cur.next;
    }
    return dummy.next;
}

let l1 = createList([2,4,3]);
let l2 = createList([5,6,4]);
let result = addTwoNumbers(l1, l2);
while (result !== null) {
    process.stdout.write(result.val + ' ');
    result = result.next;
}
console.log();

Line Notes

let dummy = new ListNode(0);Dummy node to simplify linked list construction

let carry = 0;Initialize carry for addition

while (l1 !== null || l2 !== null || carry !== 0)Loop until both lists and carry are fully processed

let val1 = l1 !== null ? l1.val : 0;Use 0 if l1 is exhausted to handle different lengths

carry = Math.floor(total / 10);Calculate carry for next digit

current.next = new ListNode(total % 10);Create new node for current digit

if (l1 !== null) l1 = l1.next;Advance l1 pointer if possible

return dummy.next;Return head of the result list, skipping dummy

⏱

Complexity

TimeO(max(m, n))

SpaceO(max(m, n))

We traverse both lists once, where m and n are their lengths. The output list length is at most max(m, n) + 1 due to carry.

💡 For lists of length 1000, this means roughly 1000 operations, which is efficient for interview constraints.

Interview Verdict: Accepted

This approach is efficient and accepted in interviews; it is the standard solution to this problem.

🧠

Recursive Approach

💡 This approach uses recursion to add digits and carry, which can be more elegant but risks stack overflow for very long lists. It helps understand the problem from a different perspective.

Intuition

Add the current digits and carry, create a node for the sum digit, then recursively add the next nodes and carry until all nodes and carry are processed.

Algorithm

1. Define a recursive function that takes two nodes and a carry.
2. If both nodes and carry are zero/null, return null (base case).
3. Sum the values of the current nodes and carry.
4. Create a new node with the digit part of the sum.
5. Recursively call the function for next nodes and updated carry.
6. Link the new node's next to the recursive call result.

💡 The recursion handles the traversal and carry propagation implicitly, but managing base cases and null nodes is critical.

</>

Code

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

def addTwoNumbersRecursive(l1, l2, carry=0):
    if not l1 and not l2 and carry == 0:
        return None
    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0
    total = val1 + val2 + carry
    carry = total // 10
    node = ListNode(total % 10)
    next1 = l1.next if l1 else None
    next2 = l2.next if l2 else None
    node.next = addTwoNumbersRecursive(next1, next2, carry)
    return node

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for num in arr:
            cur.next = ListNode(num)
            cur = cur.next
        return dummy.next

    l1 = create_list([2,4,3])
    l2 = create_list([5,6,4])
    result = addTwoNumbersRecursive(l1, l2)
    while result:
        print(result.val, end=' ')
        result = result.next
    print()

Line Notes

if not l1 and not l2 and carry == 0:Base case: no nodes and no carry means addition is complete

val1 = l1.val if l1 else 0Use 0 if l1 is exhausted to handle different lengths

total = val1 + val2 + carrySum current digits and carry

node = ListNode(total % 10)Create node for current digit

node.next = addTwoNumbersRecursive(next1, next2, carry)Recursive call for next digits and carry

return nodeReturn current node to link with previous

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode addTwoNumbersRecursive(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) return null;
        int val1 = (l1 != null) ? l1.val : 0;
        int val2 = (l2 != null) ? l2.val : 0;
        int total = val1 + val2 + carry;
        carry = total / 10;
        ListNode node = new ListNode(total % 10);
        ListNode next1 = (l1 != null) ? l1.next : null;
        ListNode next2 = (l2 != null) ? l2.next : null;
        node.next = addTwoNumbersRecursive(next1, next2, carry);
        return node;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{2,4,3});
        ListNode l2 = createList(new int[]{5,6,4});
        ListNode result = sol.addTwoNumbersRecursive(l1, l2, 0);
        printList(result);
    }

    private static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int num : arr) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

if (l1 == null && l2 == null && carry == 0) return null;Base case: no nodes and no carry means addition complete

int val1 = (l1 != null) ? l1.val : 0;Use 0 if l1 is exhausted to handle different lengths

int total = val1 + val2 + carry;Sum current digits and carry

ListNode node = new ListNode(total % 10);Create node for current digit

node.next = addTwoNumbersRecursive(next1, next2, carry);Recursive call for next digits and carry

return node;Return current node to link with previous

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbersRecursive(ListNode* l1, ListNode* l2, int carry) {
        if (!l1 && !l2 && carry == 0) return nullptr;
        int val1 = l1 ? l1->val : 0;
        int val2 = l2 ? l2->val : 0;
        int total = val1 + val2 + carry;
        carry = total / 10;
        ListNode* node = new ListNode(total % 10);
        ListNode* next1 = l1 ? l1->next : nullptr;
        ListNode* next2 = l2 ? l2->next : nullptr;
        node->next = addTwoNumbersRecursive(next1, next2, carry);
        return node;
    }
};

// Helper functions for testing
ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* node) {
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    int arr1[] = {2,4,3};
    int arr2[] = {5,6,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    ListNode* result = sol.addTwoNumbersRecursive(l1, l2, 0);
    printList(result);
    return 0;
}

Line Notes

if (!l1 && !l2 && carry == 0) return nullptr;Base case: no nodes and no carry means addition complete

int val1 = l1 ? l1->val : 0;Use 0 if l1 is exhausted to handle different lengths

int total = val1 + val2 + carry;Sum current digits and carry

ListNode* node = new ListNode(total % 10);Create node for current digit

node->next = addTwoNumbersRecursive(next1, next2, carry);Recursive call for next digits and carry

return node;Return current node to link with previous

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function addTwoNumbersRecursive(l1, l2, carry = 0) {
    if (l1 === null && l2 === null && carry === 0) return null;
    let val1 = l1 !== null ? l1.val : 0;
    let val2 = l2 !== null ? l2.val : 0;
    let total = val1 + val2 + carry;
    carry = Math.floor(total / 10);
    let node = new ListNode(total % 10);
    let next1 = l1 !== null ? l1.next : null;
    let next2 = l2 !== null ? l2.next : null;
    node.next = addTwoNumbersRecursive(next1, next2, carry);
    return node;
}

// Driver code
function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let num of arr) {
        cur.next = new ListNode(num);
        cur = cur.next;
    }
    return dummy.next;
}

let l1 = createList([2,4,3]);
let l2 = createList([5,6,4]);
let result = addTwoNumbersRecursive(l1, l2);
while (result !== null) {
    process.stdout.write(result.val + ' ');
    result = result.next;
}
console.log();

Line Notes

if (l1 === null && l2 === null && carry === 0) return null;Base case: no nodes and no carry means addition complete

let val1 = l1 !== null ? l1.val : 0;Use 0 if l1 is exhausted to handle different lengths

let total = val1 + val2 + carry;Sum current digits and carry

let node = new ListNode(total % 10);Create node for current digit

node.next = addTwoNumbersRecursive(next1, next2, carry);Recursive call for next digits and carry

return node;Return current node to link with previous

⏱

Complexity

TimeO(max(m, n))

SpaceO(max(m, n)) due to recursion stack

Each node is processed once, but recursion adds stack overhead proportional to the longer list length.

💡 For very long lists (e.g., 10^5 nodes), recursion may cause stack overflow, so iterative is safer.

Interview Verdict: Accepted but less practical for large inputs

While elegant, recursion risks stack overflow and is less preferred in interviews for large inputs.

🧠

Iterative Approach with In-Place Modification (Reusing Input Nodes)

💡 This approach optimizes space by modifying one of the input lists in place to store the result, reducing memory allocation. It is more advanced and useful when minimizing space is critical.

Intuition

Traverse both lists simultaneously, add digits and carry, and update the first list's nodes with the sum digits. If the first list ends before the second, append remaining nodes. Handle carry by adding new nodes if needed.

Algorithm

1. Use the first list as the result list, updating its nodes with sum digits.
2. Traverse both lists simultaneously, adding digits and carry.
3. If the first list ends before the second, link remaining nodes from the second list.
4. If carry remains after traversal, append a new node with carry.
5. Return the head of the modified first list.

💡 This approach requires careful pointer management to avoid losing nodes and correctly handle carry and list length differences.

</>

Code

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

def addTwoNumbersInPlace(l1, l2):
    head = l1
    carry = 0
    prev = None
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        if l1:
            l1.val = total % 10
            prev = l1
            l1 = l1.next
        else:
            prev.next = ListNode(total % 10)
            prev = prev.next
        if l2:
            l2 = l2.next
    return head

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for num in arr:
            cur.next = ListNode(num)
            cur = cur.next
        return dummy.next

    l1 = create_list([2,4,3])
    l2 = create_list([5,6,4])
    result = addTwoNumbersInPlace(l1, l2)
    while result:
        print(result.val, end=' ')
        result = result.next
    print()

Line Notes

head = l1Keep reference to head of first list to return later

carry = 0Initialize carry for addition

while l1 or l2 or carry:Loop until both lists and carry are fully processed

val1 = l1.val if l1 else 0Use 0 if l1 is exhausted to handle different lengths

val2 = l2.val if l2 else 0Use 0 if l2 is exhausted to handle different lengths

total = val1 + val2 + carrySum current digits and carry

carry = total // 10Update carry for next iteration

if l1:If first list node exists, update its value with sum digit

l1.val = total % 10Update current node of first list with sum digit

prev = l1Track last modified node to append new nodes if needed

l1 = l1.nextAdvance first list pointer

else:If first list ended, append new node with sum digit

prev.next = ListNode(total % 10)Create new node for sum digit

prev = prev.nextUpdate prev to new node

if l2:Advance second list pointer if possible

l2 = l2.nextAdvance second list pointer

return headReturn head of modified first list as result

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode addTwoNumbersInPlace(ListNode l1, ListNode l2) {
        ListNode head = l1;
        int carry = 0;
        ListNode prev = null;
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int total = val1 + val2 + carry;
            carry = total / 10;
            if (l1 != null) {
                l1.val = total % 10;
                prev = l1;
                l1 = l1.next;
            } else {
                prev.next = new ListNode(total % 10);
                prev = prev.next;
            }
            if (l2 != null) l2 = l2.next;
        }
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{2,4,3});
        ListNode l2 = createList(new int[]{5,6,4});
        ListNode result = sol.addTwoNumbersInPlace(l1, l2);
        printList(result);
    }

    private static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int num : arr) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode head = l1;Keep reference to head of first list to return result

int carry = 0;Initialize carry for addition

ListNode prev = null;Track last modified node to append new nodes if needed

while (l1 != null || l2 != null || carry != 0)Loop until both lists and carry are processed

int val1 = (l1 != null) ? l1.val : 0;Use 0 if l1 is exhausted to handle different lengths

int val2 = (l2 != null) ? l2.val : 0;Use 0 if l2 is exhausted to handle different lengths

int total = val1 + val2 + carry;Sum current digits and carry

carry = total / 10;Calculate carry for next digit

if (l1 != null) { l1.val = total % 10;Update first list node with sum digit

prev = l1;Update prev to current node

l1 = l1.next;Advance first list pointer

} else { prev.next = new ListNode(total % 10);Append new node if first list ended

prev = prev.next;Update prev to new node

if (l2 != null) l2 = l2.next;Advance second list pointer if possible

return head;Return head of modified first list

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbersInPlace(ListNode* l1, ListNode* l2) {
        ListNode* head = l1;
        ListNode* prev = nullptr;
        int carry = 0;
        while (l1 || l2 || carry) {
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            int total = val1 + val2 + carry;
            carry = total / 10;
            if (l1) {
                l1->val = total % 10;
                prev = l1;
                l1 = l1->next;
            } else {
                prev->next = new ListNode(total % 10);
                prev = prev->next;
            }
            if (l2) l2 = l2->next;
        }
        return head;
    }
};

// Helper functions for testing
ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* node) {
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    int arr1[] = {2,4,3};
    int arr2[] = {5,6,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    ListNode* result = sol.addTwoNumbersInPlace(l1, l2);
    printList(result);
    return 0;
}

Line Notes

ListNode* head = l1;Keep reference to head of first list to return result

ListNode* prev = nullptr;Track last modified node to append new nodes if needed

int carry = 0;Initialize carry for addition

while (l1 || l2 || carry)Loop until both lists and carry are processed

int val1 = l1 ? l1->val : 0;Use 0 if l1 is exhausted to handle different lengths

int val2 = l2 ? l2->val : 0;Use 0 if l2 is exhausted to handle different lengths

int total = val1 + val2 + carry;Sum current digits and carry

carry = total / 10;Calculate carry for next digit

if (l1) { l1->val = total % 10;Update first list node with sum digit

prev = l1;Update prev to current node

l1 = l1->next;Advance first list pointer

} else { prev->next = new ListNode(total % 10);Append new node if first list ended

prev = prev->next;Update prev to new node

if (l2) l2 = l2->next;Advance second list pointer if possible

return head;Return head of modified first list

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function addTwoNumbersInPlace(l1, l2) {
    let head = l1;
    let carry = 0;
    let prev = null;
    while (l1 !== null || l2 !== null || carry !== 0) {
        let val1 = l1 !== null ? l1.val : 0;
        let val2 = l2 !== null ? l2.val : 0;
        let total = val1 + val2 + carry;
        carry = Math.floor(total / 10);
        if (l1 !== null) {
            l1.val = total % 10;
            prev = l1;
            l1 = l1.next;
        } else {
            prev.next = new ListNode(total % 10);
            prev = prev.next;
        }
        if (l2 !== null) l2 = l2.next;
    }
    return head;
}

// Driver code
function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let num of arr) {
        cur.next = new ListNode(num);
        cur = cur.next;
    }
    return dummy.next;
}

let l1 = createList([2,4,3]);
let l2 = createList([5,6,4]);
let result = addTwoNumbersInPlace(l1, l2);
while (result !== null) {
    process.stdout.write(result.val + ' ');
    result = result.next;
}
console.log();

Line Notes

let head = l1;Keep reference to head of first list to return result

let carry = 0;Initialize carry for addition

let prev = null;Track last modified node to append new nodes if needed

while (l1 !== null || l2 !== null || carry !== 0)Loop until both lists and carry are processed

let val1 = l1 !== null ? l1.val : 0;Use 0 if l1 is exhausted to handle different lengths

let val2 = l2 !== null ? l2.val : 0;Use 0 if l2 is exhausted to handle different lengths

let total = val1 + val2 + carry;Sum current digits and carry

carry = Math.floor(total / 10);Calculate carry for next digit

if (l1 !== null) { l1.val = total % 10;Update first list node with sum digit

prev = l1;Update prev to current node

l1 = l1.next;Advance first list pointer

} else { prev.next = new ListNode(total % 10);Append new node if first list ended

prev = prev.next;Update prev to new node

if (l2 !== null) l2 = l2.next;Advance second list pointer if possible

return head;Return head of modified first list

⏱

Complexity

TimeO(max(m, n))

SpaceO(1) additional space (in-place modification)

We traverse both lists once and reuse nodes from the first list, so no extra list nodes are created except possibly one for carry.

💡 This approach is more memory efficient, especially for large inputs, but requires careful pointer handling.

Interview Verdict: Accepted, space optimized

This is an advanced approach that saves space by reusing input nodes, useful when memory is constrained.

📊

All Approaches - One-Glance Tradeoffs

💡 The iterative approach with dummy head is the best balance of clarity and efficiency and should be your go-to in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Iterative with dummy head)	O(max(m, n))	O(max(m, n))	No	N/A	Code this approach in interviews
2. Recursive Approach	O(max(m, n))	O(max(m, n)) due to recursion stack	Yes (for large inputs)	N/A	Mention as alternative, avoid coding for large inputs
3. Iterative In-Place Modification	O(max(m, n))	O(1) additional space	No	N/A	Mention if allowed to modify inputs; code if asked for space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and finally discuss optimizations. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach simulating addition digit by digit.Step 3: Write clean, iterative code with a dummy head and carry handling.Step 4: Test your code with sample and edge cases.Step 5: Discuss recursive and in-place optimizations if time permits.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of linked list traversal, carry management, edge case handling, and clean code writing.

Common Follow-ups

• What if digits are stored in forward order? → Use stack or reverse lists first.
• Can you do this without extra space? → Modify one list in place as shown.

💡 These follow-ups test your ability to adapt the solution to variations and optimize space.

🔍

Pattern Recognition

When to Use

Use this pattern when you have two linked lists representing numbers in reverse order and need to add them digit by digit with carry.

Signature Phrases

'digits are stored in reverse order''each node contains a single digit''add the two numbers and return the sum as a linked list'

NOT This Pattern When

Problems involving linked list merging or sorting without digit arithmetic are different patterns.

Similar Problems

Multiply Strings - similar digit-by-digit arithmetic but with stringsAdd Two Numbers II - digits stored in forward order, requiring different approachSum Lists - similar addition but may differ in list order or carry handling

Practice

1. You are given a sorted linked list where some elements appear more than once consecutively. The task is to remove all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Which approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to compare each node with all others and remove duplicates.

B. Use a single-pass iterative approach with a dummy head to skip all duplicates in one traversal.

C. Use a greedy approach that removes duplicates as soon as they are found without revisiting nodes.

D. Use dynamic programming to store counts of each value and then reconstruct the list.

Solution

1. Step 1: Understand problem constraints

   The list is sorted, so duplicates appear consecutively, enabling a single pass to detect and skip duplicates.

2. Step 2: Evaluate approaches

   Brute force nested loops are inefficient (O(n²)). Greedy removal without revisiting can leave some duplicates. DP is unnecessary and inefficient here. The single-pass iterative approach with a dummy head efficiently removes all duplicates in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with dummy head handles duplicates correctly [OK]

Hint: Sorted list allows single-pass duplicate skipping [OK]

Common Mistakes:

• Thinking greedy removal is enough
• Using nested loops unnecessarily
• Applying DP to a linked list problem

2. Given the following recursive code to remove the 2nd node from the end of the list 1 -> 2 -> 3 -> 4, what is the final printed output?

easy

A. 1 2 3 4

B. 1 3 4

C. 2 3 4

D. 1 2 4

Solution

1. Step 1: Trace recursion calls

   Recursion counts from end: node 4 returns 1, node 3 returns 2, node 2 returns 3, node 1 returns 4.

2. Step 2: Identify node to remove

   When count is n+1=3, node.next is removed. At node 2 (count=3), node.next (node 3) is skipped, so node 3 is removed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches list with 3 removed: 1 2 4 [OK]

Hint: Recursion count matches position from end [OK]

Common Mistakes:

• Off-by-one in recursion count
• Removing wrong node due to incorrect condition
• Not handling dummy node correctly

3. Given the following tail-recursive reversal code, what is the output printed when the input linked list is 1 -> 2 -> 3?

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

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

head = ListNode(1, ListNode(2, ListNode(3)))
new_head = reverseList(head)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next
print()

easy

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Trace helper calls

   Initial call: helper(None, node1(1)) - next_temp = node2(2) - node1.next = None - call helper(node1, node2) Next call: helper(node1, node2) - next_temp = node3(3) - node2.next = node1 - call helper(node2, node3) Next call: helper(node2, node3) - next_temp = None - node3.next = node2 - call helper(node3, None) Next call: helper(node3, None) returns node3 as new head.

2. Step 2: Print reversed list

   Starting from node3, print values: 3 -> 2 -> 1

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversal correctly outputs 3 2 1 [OK]

Hint: Pointers reversed during recursion descent [OK]

Common Mistakes:

• Confusing original order with reversed output
• Off-by-one in pointer updates

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

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