#2

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Add Two Numbers

Add Two Numbers requires careful linked-list pointer manipulation to sum digits while handling carries efficiently in interview settings.

linked list math recursion

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Simulation

We traverse two linked lists $l_1$ and $l_2$ at the same time, and use the variable $carry$ to indicate whether there is a carry.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode()
        carry, curr = 0, dummy
        while l1 or l2 or carry:
            s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, val = divmod(s, 10)
            curr.next = ListNode(val)
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

Continue Practicing

#21 merge two sorted lists #24 swap nodes in pairs #25 reverse nodes in k group