How to Solve Add Two Numbers

This problem emphasizes manipulating linked-list pointers to add corresponding digits and manage carries recursively or iteratively. GhostInterview guides you step-by-step through node traversal, ensuring the sum reflects both short and long lists. By following pointer updates carefully, you avoid common mistakes such as misaligned carry handling or skipping nodes, delivering a correct and optimal linked-list result.

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, with each node containing a single digit. Your task is to add the two numbers and return the sum as a linked list, maintaining reverse order digit storage.

Assume that the numbers do not contain leading zeros except when the number is 0 itself. For example, adding l1 = [2,4,3] and l2 = [5,6,4] should produce [7,0,8] because 342 + 465 = 807. Each linked list may have a different length, so pointer traversal and carry propagation must handle uneven lists correctly.

Examples

Example 1

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

Output: [7,0,8]

342 + 465 = 807.

Example 2

Input: l1 = [0], l2 = [0]

Output: [0]

Example details omitted.

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

Example details omitted.

Constraints

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution Approach

Iterative Pointer Traversal

Use two pointers to traverse l1 and l2 simultaneously, summing node values and carry at each step. Append new nodes for each sum modulo 10, and propagate carry forward. Continue until both lists are fully processed, then append any remaining carry as a new node.

Recursive Addition

Define a recursive function that adds current nodes and the carry, then calls itself with next nodes. Base case returns null when all nodes are processed. This approach naturally handles lists of different lengths but requires careful carry propagation in each recursive return.

Handling Unequal Lengths and Edge Cases

Pad shorter list conceptually or treat missing nodes as zeros during addition. Always check for final carry to append a new node at the end. This ensures correctness when adding numbers like [9,9,9,9,9,9,9] + [9,9,9,9], preventing off-by-one errors in node creation.

Complexity Analysis

Time complexity is O(max(m,n)) where m and n are the lengths of the two lists, as each node is visited once. Space complexity is O(max(m,n)) for iterative solutions due to result list allocation, and O(max(m,n)) for recursive solutions due to call stack usage.

What Interviewers Usually Probe

• Check how you handle carries at each node and whether your pointers correctly traverse both lists.
• Notice if you address unequal list lengths without skipping nodes or losing digits.
• Consider whether your recursive or iterative approach maintains clarity and avoids unnecessary node allocations.

Common Pitfalls or Variants

Common pitfalls

• Failing to propagate carry to a new node after both lists are processed.
• Misaligning pointers when lists have different lengths, leading to incorrect sums.
• Forgetting that a null node should be treated as zero during addition, causing off-by-one errors.

Follow-up variants

• Add numbers where digits are stored in forward order, requiring reversal before pointer traversal.
• Perform addition without modifying the original lists, creating a fully new result list.
• Implement addition using constant space by reusing existing nodes and careful pointer updates.

How GhostInterview Helps

• Guides pointer-by-pointer addition for accurate carry handling across different list lengths.
• Provides stepwise debugging for both iterative and recursive approaches, preventing off-by-one mistakes.
• Explains trade-offs between creating new nodes versus reusing existing ones for memory-efficient solutions.

Topic Pages

• Linked List
• Math
• Recursion

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best way to handle carry in Add Two Numbers linked list addition?

Track carry separately during node summation and always check for a final carry after traversing both lists, adding a new node if needed.

Can Add Two Numbers be solved recursively?

Yes, recursion naturally handles node traversal and carry propagation, but you must manage base cases and list length differences carefully.

What should I do if the two input lists are of different lengths?

Treat missing nodes as zeros during addition or conceptually pad the shorter list, ensuring pointers advance correctly without skipping nodes.

Does GhostInterview cover iterative pointer manipulation for this problem?

Yes, it shows detailed steps for pointer traversal, sum calculation, carry management, and node appending for iterative solutions.

Why is linked-list pointer manipulation crucial in Add Two Numbers?

Because each digit is in a separate node, careful pointer movement ensures correct alignment, sum computation, and carry propagation across unequal lists.