Add Two Numbers II (MSB First)

🎯

Add Two Numbers II (MSB First)

mediumLINKED_LISTAmazonGoogle

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?

💡 This problem is about adding two numbers represented as linked lists where the most significant digit comes first. Beginners often struggle because unlike the simpler version where digits are reversed, here you cannot just add from head to tail easily. Understanding how to handle carry and traversal order is key.

📋

Problem Statement

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.

💡

Example

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

Output[7,8,0,7]

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

• Both lists have only one node with 0 → output 0
• One list is significantly longer than the other → correct carry handling
• Sum results in an extra digit (e.g., 999 + 1 = 1000) → output list longer than inputs
• Lists with leading zeros (not allowed by constraints but test robustness) → should still work

⚠️

Common Mistakes

Reversing input lists without copying

Modifies input lists unexpectedly, may cause bugs if inputs are reused

✅ Use stacks or recursion to avoid modifying inputs

Not handling carry after final addition

Missing leading digit in result, e.g., 999 + 1 returns 000 instead of 1000

✅ Check carry after loop/recursion and add new node if needed

Incorrect padding of shorter list

Misaligned addition leading to wrong sums

✅ Calculate lengths and pad shorter list with zeros at front before addition

Stack underflow or empty stack pop

Runtime errors or incorrect sums

✅ Check if stack is empty before popping, use 0 if empty

Not updating pointers correctly when building result list

Result list is malformed or reversed incorrectly

✅ Insert new nodes at front and update head pointer properly

🧠

Brute Force (Reverse Lists and Add)

💡 This approach exists because reversing the lists transforms the problem into the simpler 'Add Two Numbers' problem where digits are stored least significant first. It helps beginners understand the problem by reducing it to a known simpler variant.

Intuition

Reverse both linked lists to get least significant digits first, add them like normal, then reverse the result to restore forward order.

Algorithm

1. Reverse both input linked lists.
2. Add the two reversed lists digit by digit, managing carry.
3. Reverse the resulting list to restore forward order.
4. Return the final summed list.

💡 The main challenge is realizing reversing simplifies addition but requires extra passes and modifies input if not careful.

</>

Code

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

def addTwoNumbers(l1, l2):
    l1 = reverseList(l1)
    l2 = reverseList(l2)
    carry = 0
    head = 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
        node = ListNode(total % 10)
        node.next = head
        head = node
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    return head

# Driver code to test
if __name__ == '__main__':
    # Helper to create list
    def create_list(arr):
        head = None
        for val in reversed(arr):
            head = ListNode(val, head)
        return head

    # Helper to print list
    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([7,2,4,3])
    l2 = create_list([5,6,4])
    res = addTwoNumbers(l1, l2)
    print_list(res)

Line Notes

def reverseList(head):Defines helper to reverse a linked list, key to simplifying addition

while curr:Traverse the list to reverse pointers one by one

curr.next = prevReverse current node's pointer to previous node

l1 = reverseList(l1)Reverse first input list to start addition from least significant digit

carry = 0Initialize carry for addition

while l1 or l2 or carry:Loop until all digits and carry are processed

node.next = headInsert new node at front to build reversed sum list

return headReturn the final summed list in forward order

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

public class Solution {
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        int carry = 0;
        ListNode head = null;
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return head;
    }

    // Main method to test
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode res = sol.addTwoNumbers(l1, l2);
        while (res != null) {
            System.out.print(res.val);
            if (res.next != null) System.out.print(",");
            res = res.next;
        }
        System.out.println();
    }
}

Line Notes

private ListNode reverseList(ListNode head)Helper method to reverse linked list for easier addition

while (curr != null)Traverse nodes to reverse pointers

curr.next = prevReverse pointer direction for current node

l1 = reverseList(l1)Reverse first input list to add from least significant digit

int carry = 0;Initialize carry for digit addition

while (l1 != null || l2 != null || carry != 0)Loop until all digits and carry processed

node.next = head;Insert new node at front to build result in forward order

return head;Return final summed list

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        int carry = 0;
        ListNode* head = nullptr;
        while (l1 || l2 || carry) {
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = head;
            head = node;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        return head;
    }
};

// Driver code
int main() {
    Solution sol;
    ListNode* l1 = new ListNode(7);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);
    l1->next->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode* res = sol.addTwoNumbers(l1, l2);
    while (res) {
        cout << res->val;
        if (res->next) cout << ",";
        res = res->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* reverseList(ListNode* head)Helper to reverse linked list for easier addition

while (curr)Traverse nodes to reverse pointers

curr->next = prev;Reverse pointer direction for current node

l1 = reverseList(l1);Reverse first input list to add from least significant digit

int carry = 0;Initialize carry for addition

while (l1 || l2 || carry)Loop until all digits and carry processed

node->next = head;Insert new node at front to build result in forward order

return head;Return final summed list

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

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

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

// Test code
function createList(arr) {
    let head = null;
    for (let i = arr.length - 1; i >= 0; i--) {
        head = new ListNode(arr[i], head);
    }
    return head;
}

function printList(node) {
    let vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

const l1 = createList([7,2,4,3]);
const l2 = createList([5,6,4]);
const res = addTwoNumbers(l1, l2);
printList(res);

Line Notes

function reverseList(head)Helper to reverse linked list for easier addition

while (curr)Traverse nodes to reverse pointers

curr.next = prev;Reverse pointer direction for current node

l1 = reverseList(l1);Reverse first input list to add from least significant digit

let carry = 0;Initialize carry for addition

while (l1 || l2 || carry)Loop until all digits and carry processed

node.next = head;Insert new node at front to build result in forward order

return head;Return final summed list

⏱

Complexity

TimeO(n + m)

SpaceO(n + m)

Reversing each list takes O(n) and O(m), addition is O(max(n,m)), and building the result is O(n+m).

💡 For lists of length 100,000, this means about 300,000 operations, which is efficient enough but requires extra passes.

Interview Verdict: Accepted

This approach works well but modifies input lists by reversing, which might not be allowed in some interviews.

🧠

Using Stacks to Simulate Reverse Traversal

💡 This approach avoids reversing the input lists by using stacks to process digits from least significant to most significant, preserving input integrity.

Intuition

Push all digits of both lists onto stacks, then pop from stacks to add digits from least significant to most significant, managing carry.

Algorithm

1. Push all nodes' values from both lists onto two separate stacks.
2. Pop values from both stacks, add them with carry.
3. Create new nodes for each digit of the sum and link them at the front.
4. Return the head of the newly formed list.

💡 Stacks let you process digits in reverse order without modifying the input lists, which is often a requirement.

</>

Code

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

def addTwoNumbers(l1, l2):
    stack1, stack2 = [], []
    while l1:
        stack1.append(l1.val)
        l1 = l1.next
    while l2:
        stack2.append(l2.val)
        l2 = l2.next
    carry = 0
    head = None
    while stack1 or stack2 or carry:
        val1 = stack1.pop() if stack1 else 0
        val2 = stack2.pop() if stack2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        node = ListNode(total % 10)
        node.next = head
        head = node
    return head

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        head = None
        for val in reversed(arr):
            head = ListNode(val, head)
        return head

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([7,2,4,3])
    l2 = create_list([5,6,4])
    res = addTwoNumbers(l1, l2)
    print_list(res)

Line Notes

stack1, stack2 = [], []Initialize stacks to hold digits for reverse processing

while l1:Push all digits of first list onto stack1 to simulate reverse traversal

while l2:Push all digits of second list onto stack2 to simulate reverse traversal

while stack1 or stack2 or carry:Process all digits and carry until done

val1 = stack1.pop() if stack1 else 0Pop digit from stack1 or use 0 if empty to handle unequal lengths

val2 = stack2.pop() if stack2 else 0Pop digit from stack2 or use 0 if empty

node.next = headInsert new node at front to build result in forward order

return headReturn the summed list preserving input order

import java.util.Stack;

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

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int val1 = stack1.isEmpty() ? 0 : stack1.pop();
            int val2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
        }
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode res = sol.addTwoNumbers(l1, l2);
        while (res != null) {
            System.out.print(res.val);
            if (res.next != null) System.out.print(",");
            res = res.next;
        }
        System.out.println();
    }
}

Line Notes

Stack<Integer> stack1 = new Stack<>();Create stack to hold digits of first list for reverse processing

while (l1 != null)Push all digits of first list onto stack1

while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0)Process all digits and carry until complete

int val1 = stack1.isEmpty() ? 0 : stack1.pop();Pop digit from stack1 or use 0 if empty to handle different lengths

node.next = head;Insert new node at front to build result in forward order

return head;Return the summed list preserving input order

#include <iostream>
#include <stack>
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) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int carry = 0;
        ListNode* head = nullptr;
        while (!s1.empty() || !s2.empty() || carry) {
            int val1 = s1.empty() ? 0 : s1.top();
            if (!s1.empty()) s1.pop();
            int val2 = s2.empty() ? 0 : s2.top();
            if (!s2.empty()) s2.pop();
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = head;
            head = node;
        }
        return head;
    }
};

int main() {
    Solution sol;
    ListNode* l1 = new ListNode(7);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);
    l1->next->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode* res = sol.addTwoNumbers(l1, l2);
    while (res) {
        cout << res->val;
        if (res->next) cout << ",";
        res = res->next;
    }
    cout << endl;
    return 0;
}

Line Notes

stack<int> s1, s2;Stacks to hold digits of input lists for reverse processing

while (l1)Push all digits of first list onto stack s1

while (!s1.empty() || !s2.empty() || carry)Process all digits and carry until complete

int val1 = s1.empty() ? 0 : s1.top();Get digit from stack s1 or 0 if empty

if (!s1.empty()) s1.pop();Pop digit from stack s1 after reading

node->next = head;Insert new node at front to build result in forward order

return head;Return final summed list preserving input order

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

function addTwoNumbers(l1, l2) {
    const stack1 = [];
    const stack2 = [];
    while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    let carry = 0;
    let head = null;
    while (stack1.length > 0 || stack2.length > 0 || carry > 0) {
        const val1 = stack1.length > 0 ? stack1.pop() : 0;
        const val2 = stack2.length > 0 ? stack2.pop() : 0;
        const sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10);
        const node = new ListNode(sum % 10);
        node.next = head;
        head = node;
    }
    return head;
}

// Test code
function createList(arr) {
    let head = null;
    for (let i = arr.length - 1; i >= 0; i--) {
        head = new ListNode(arr[i], head);
    }
    return head;
}

function printList(node) {
    const vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

const l1 = createList([7,2,4,3]);
const l2 = createList([5,6,4]);
const res = addTwoNumbers(l1, l2);
printList(res);

Line Notes

const stack1 = [];Stack to hold digits of first list for reverse processing

while (l1)Push all digits of first list onto stack1

while (stack1.length > 0 || stack2.length > 0 || carry > 0)Process all digits and carry until complete

const val1 = stack1.length > 0 ? stack1.pop() : 0;Pop digit from stack1 or use 0 if empty

node.next = head;Insert new node at front to build result in forward order

return head;Return final summed list preserving input order

⏱

Complexity

TimeO(n + m)

SpaceO(n + m)

Pushing all digits onto stacks and popping them is O(n + m), building the result is also O(n + m).

💡 For input lists of length 100,000, this approach uses extra memory for stacks but avoids modifying inputs.

Interview Verdict: Accepted

This approach is preferred when input lists must not be modified and is efficient enough for large inputs.

🧠

Recursive Length Alignment and Addition Without Extra Space

💡 This approach aligns the two lists by length and recursively adds corresponding nodes, handling carry on the way back. It avoids extra data structures but is more complex.

Intuition

Pad the shorter list with zeros, recursively add nodes from most significant to least significant, propagate carry back up the recursion stack.

Algorithm

1. Calculate lengths of both lists.
2. Pad the shorter list with zeros at the front to match lengths.
3. Recursively add corresponding nodes starting from the head.
4. Propagate carry back up and create new head if needed.

💡 This approach is harder because you must manage padding and carry propagation recursively, but it uses no extra stacks or reversal.

</>

Code

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

def getLength(head):
    length = 0
    while head:
        length += 1
        head = head.next
    return length

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

def addListsHelper(l1, l2):
    if not l1 and not l2:
        return (None, 0)
    next_node, carry = addListsHelper(l1.next, l2.next)
    total = l1.val + l2.val + carry
    node = ListNode(total % 10)
    node.next = next_node
    return (node, total // 10)

def addTwoNumbers(l1, l2):
    len1 = getLength(l1)
    len2 = getLength(l2)
    if len1 < len2:
        l1 = padList(l1, len2 - len1)
    else:
        l2 = padList(l2, len1 - len2)
    head, carry = addListsHelper(l1, l2)
    if carry:
        head = ListNode(carry, head)
    return head

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        head = None
        for val in reversed(arr):
            head = ListNode(val, head)
        return head

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([7,2,4,3])
    l2 = create_list([5,6,4])
    res = addTwoNumbers(l1, l2)
    print_list(res)

Line Notes

def getLength(head):Helper to find length of linked list for padding

def padList(head, padding):Add zeros in front to equalize lengths

def addListsHelper(l1, l2):Recursive helper to add nodes and carry

next_node, carry = addListsHelper(l1.next, l2.next)Recursive call to process next digits first

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

if carry:If carry remains after full addition, add new head node

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

public class Solution {
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    private ListNode padList(ListNode head, int padding) {
        for (int i = 0; i < padding; i++) {
            ListNode node = new ListNode(0);
            node.next = head;
            head = node;
        }
        return head;
    }

    private class SumResult {
        ListNode node;
        int carry;
        SumResult(ListNode node, int carry) {
            this.node = node;
            this.carry = carry;
        }
    }

    private SumResult addListsHelper(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return new SumResult(null, 0);
        SumResult next = addListsHelper(l1.next, l2.next);
        int sum = l1.val + l2.val + next.carry;
        ListNode node = new ListNode(sum % 10);
        node.next = next.node;
        return new SumResult(node, sum / 10);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        if (len1 < len2) l1 = padList(l1, len2 - len1);
        else l2 = padList(l2, len1 - len2);
        SumResult res = addListsHelper(l1, l2);
        if (res.carry != 0) {
            ListNode node = new ListNode(res.carry);
            node.next = res.node;
            return node;
        }
        return res.node;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode res = sol.addTwoNumbers(l1, l2);
        while (res != null) {
            System.out.print(res.val);
            if (res.next != null) System.out.print(",");
            res = res.next;
        }
        System.out.println();
    }
}

Line Notes

private int getLength(ListNode head)Calculate length to pad shorter list

private ListNode padList(ListNode head, int padding)Add zeros at front to equalize lengths

private SumResult addListsHelper(ListNode l1, ListNode l2)Recursive addition returning node and carry

SumResult next = addListsHelper(l1.next, l2.next);Process next digits first to handle carry

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

if (res.carry != 0)Add new head if carry remains after recursion

#include <iostream>
using namespace std;

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

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            length++;
            head = head->next;
        }
        return length;
    }

    ListNode* padList(ListNode* head, int padding) {
        for (int i = 0; i < padding; i++) {
            ListNode* node = new ListNode(0);
            node->next = head;
            head = node;
        }
        return head;
    }

    struct SumResult {
        ListNode* node;
        int carry;
        SumResult(ListNode* n, int c) : node(n), carry(c) {}
    };

    SumResult addListsHelper(ListNode* l1, ListNode* l2) {
        if (!l1 && !l2) return SumResult(nullptr, 0);
        SumResult next = addListsHelper(l1->next, l2->next);
        int sum = l1->val + l2->val + next.carry;
        ListNode* node = new ListNode(sum % 10);
        node->next = next.node;
        return SumResult(node, sum / 10);
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        if (len1 < len2) l1 = padList(l1, len2 - len1);
        else l2 = padList(l2, len1 - len2);
        SumResult res = addListsHelper(l1, l2);
        if (res.carry != 0) {
            ListNode* node = new ListNode(res.carry);
            node->next = res.node;
            return node;
        }
        return res.node;
    }
};

int main() {
    Solution sol;
    ListNode* l1 = new ListNode(7);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);
    l1->next->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode* res = sol.addTwoNumbers(l1, l2);
    while (res) {
        cout << res->val;
        if (res->next) cout << ",";
        res = res->next;
    }
    cout << endl;
    return 0;
}

Line Notes

int getLength(ListNode* head)Calculate length to pad shorter list

ListNode* padList(ListNode* head, int padding)Add zeros at front to equalize lengths

SumResult addListsHelper(ListNode* l1, ListNode* l2)Recursive addition returning node and carry

SumResult next = addListsHelper(l1->next, l2->next);Process next digits first to handle carry

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

if (res.carry != 0)Add new head if carry remains after recursion

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

function getLength(head) {
    let length = 0;
    while (head) {
        length++;
        head = head.next;
    }
    return length;
}

function padList(head, padding) {
    for (let i = 0; i < padding; i++) {
        head = new ListNode(0, head);
    }
    return head;
}

function addListsHelper(l1, l2) {
    if (!l1 && !l2) return { node: null, carry: 0 };
    const next = addListsHelper(l1.next, l2.next);
    const sum = l1.val + l2.val + next.carry;
    const node = new ListNode(sum % 10);
    node.next = next.node;
    return { node: node, carry: Math.floor(sum / 10) };
}

function addTwoNumbers(l1, l2) {
    const len1 = getLength(l1);
    const len2 = getLength(l2);
    if (len1 < len2) l1 = padList(l1, len2 - len1);
    else l2 = padList(l2, len1 - len2);
    const res = addListsHelper(l1, l2);
    if (res.carry) {
        return new ListNode(res.carry, res.node);
    }
    return res.node;
}

// Test code
function createList(arr) {
    let head = null;
    for (let i = arr.length - 1; i >= 0; i--) {
        head = new ListNode(arr[i], head);
    }
    return head;
}

function printList(node) {
    const vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

const l1 = createList([7,2,4,3]);
const l2 = createList([5,6,4]);
const res = addTwoNumbers(l1, l2);
printList(res);

Line Notes

function getLength(head)Calculate length to pad shorter list

function padList(head, padding)Add zeros at front to equalize lengths

function addListsHelper(l1, l2)Recursive addition returning node and carry

const next = addListsHelper(l1.next, l2.next);Process next digits first to handle carry

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

if (res.carry)Add new head if carry remains after recursion

⏱

Complexity

TimeO(n + m)

SpaceO(n + m) due to recursion stack

Padding and length calculation are O(n + m), recursion depth is O(n), building result is O(n).

💡 For input size 100,000, recursion depth is large but acceptable in many environments; no extra data structures used.

Interview Verdict: Accepted

This approach is elegant and uses no extra data structures but requires careful recursion and padding logic.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the stack-based approach is best to code: it respects input immutability, is intuitive, and efficient.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Reverse Lists and Add)	O(n + m)	O(1) extra but modifies input	No	Yes	Mention only - may violate input constraints
2. Using Stacks to Simulate Reverse Traversal	O(n + m)	O(n + m) for stacks	No	Yes	Preferred approach to code in interviews
3. Recursive Length Alignment and Addition	O(n + m)	O(n + m) recursion stack	Yes (deep recursion)	Yes	Good to discuss for in-place addition without extra data structures

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying input/output, then explain brute force, and progressively optimize. Practice coding and testing all approaches.

How to Present

Clarify the problem and constraints, especially about modifying input lists.State the brute force approach: reverse lists, add, reverse result.Discuss why reversing might not be allowed and introduce stack-based approach.Explain recursive length alignment approach for in-place addition.Code the chosen approach carefully, test with edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of linked list manipulation, carry handling, and ability to optimize space/time while respecting constraints.

Common Follow-ups

• What if input lists are immutable? → Use stacks or recursion without reversing.
• Can you do it without extra space? → Recursive length alignment approach.

💡 Follow-ups often test your ability to handle constraints like immutability or optimize space, so be ready to discuss alternative approaches.

🔍

Pattern Recognition

When to Use

1) Input is two linked lists representing numbers; 2) digits stored most significant first; 3) no reversal allowed; 4) need to add and return sum as linked list.

Signature Phrases

'digits are stored in forward order''add the two numbers and return the sum as a linked list'

NOT This Pattern When

Problems where digits are stored least significant first or where arrays/strings are used instead of linked lists.

Similar Problems

Add Two Numbers (LeetCode 2) - same problem but digits reversedSum Lists (Cracking the Coding Interview) - similar addition with linked listsMultiply Strings - handling carry without direct integer conversion

Practice

1. What is the time complexity of the two-pointer length equalization approach to find the intersection node of two singly linked lists with lengths m and n, respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(max(m, n) * 2)

D. O(m + n + k), where k is the length of the intersection

Solution

1. Step 1: Identify loop iterations

   Each pointer traverses its list once, then switches to the other list, traversing at most m + n nodes.

2. Step 2: Simplify complexity

   Total steps are proportional to m + n, so time complexity is O(m + n). O(m * n) is brute force, O(max(m, n) * 2) simplifies to O(m + n), and O(m + n + k) adds an unnecessary term.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach is linear in combined list lengths [OK]

Hint: Pointers traverse each list once plus switch [OK]

Common Mistakes:

• Confusing nested loops with two-pointer approach
• Counting intersection length separately
• Misreading max(m,n) as multiplication

2. The following code attempts to merge k sorted linked lists using a min-heap. Identify the line that contains a subtle bug that can cause incorrect merging or runtime errors.

medium

A. Line: current.next = smallest

B. Line: Missing 'current = current.next' after attaching smallest

C. Line: while heap:

D. Line: if node: heapq.heappush(heap, node)

Solution

1. Step 1: Review pointer updates in loop

   After attaching smallest to current.next, current must move forward.

2. Step 2: Identify missing line

   Code lacks 'current = current.next', so current stays, causing incorrect list linking.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing current, merged list nodes overwrite each other [OK]

Hint: Always advance current pointer after attaching a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Misplacing heap push conditions
• Confusing heap pop with list traversal

3. What is the time and space complexity of the recursive approach to reverse a sublist between positions left and right in a singly linked list of length n?

medium

A. Time: O(n), Space: O(1) due to in-place reversal

B. Time: O(n^2), Space: O(n) due to repeated traversals

C. Time: O(right - left), Space: O(right - left) due to partial recursion

D. Time: O(n), Space: O(n) due to recursion stack

Solution

1. Step 1: Analyze time complexity

   The recursive approach visits each node at most once, so time complexity is O(n).

2. Step 2: Analyze space complexity

   Recursion depth can be up to n in worst case, so space complexity is O(n) due to recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space is often overlooked but critical here [OK]

Hint: Recursion adds O(n) space, not O(1) [OK]

Common Mistakes:

• Assuming constant space for in-place reversal
• Confusing partial recursion depth with full list length
• Mistaking time complexity as quadratic

4. What is the space complexity of the tail-recursive reversal approach for reversing a singly linked list of length n, and why might a common misconception about it be incorrect?

medium

A. O(1) because the reversal is done in-place with constant extra pointers.

B. O(n) because the recursion stack grows linearly with the list length.

C. O(n) because an auxiliary array is used to store nodes during reversal.

D. O(log n) because tail recursion optimizes the stack usage to logarithmic depth.

Solution

1. Step 1: Identify recursion stack usage

   Each recursive call adds a frame to the call stack until the base case is reached, so for n nodes, stack depth is n.

2. Step 2: Analyze auxiliary space

   No extra arrays or data structures are used, so auxiliary space besides recursion stack is O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursion stack causes O(n) space, not constant [OK]

Hint: Recursion stack adds O(n) space despite in-place pointer changes [OK]

Common Mistakes:

• Assuming tail recursion is optimized to O(1) stack in Python
• Confusing auxiliary data structures with recursion stack

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly). Which modification to the palindrome check algorithm ensures correctness without corrupting the list or causing infinite loops?

hard

A. Reverse the second half in-place and restore it after comparison to preserve list structure.

B. Use the brute force approach converting to an array to avoid modifying the list.

C. Use the recursive two-pointer technique without any changes since it does not modify the list.

D. Use a fast and slow pointer to detect cycles and return False immediately if a cycle exists.

Solution

1. Step 1: Understand the problem with node reuse

   Reusing nodes or cyclic lists mean in-place reversal must restore the list to avoid corruption or infinite loops.

2. Step 2: Identify the approach that preserves list integrity

   Reversing the second half and restoring it after comparison ensures the original list remains unchanged and safe for reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Restoring reversed half prevents side effects on reused lists [OK]

Hint: Restoring reversed half preserves list for reuse [OK]

Common Mistakes:

• Assuming recursive approach never modifies list
• Ignoring cycle detection
• Using brute force wastes space unnecessarily