Add Two Numbers

Mediumlinked-listmath
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookBloombergGoogle
LeetCode →NeetCode →

Approach

Add Two Numbers

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Examples

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example 2

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

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]

Intuition

Key Observation: Digits are in reverse order, which makes addition easier!

For 342 + 465:

  • List representation: [2,4,3] + [5,6,4]
  • Add from left to right (ones place first)
  • Handle carry to next position

Why Reverse Order Helps:

  • Addition starts from least significant digit (rightmost)
  • Carry propagates left
  • Reverse order means we can traverse lists naturally

Pattern Recognition

This is a Linked List Arithmetic problem:

  • Simulate addition algorithm
  • Track carry between digits
  • Handle different lengths
  • Create new list for result

Approach

def addTwoNumbers(self, l1, l2):
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        # Get values (0 if list ended)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Calculate sum and carry
        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        # Create new node
        curr.next = ListNode(digit)
        curr = curr.next

        # Move to next nodes
        if l1: l1 = l1.next
        if l2: l2 = l2.next

    return dummy.next

Complexity Analysis

  • Time: O(max(m, n))

    • m = length of l1, n = length of l2
    • Process each digit once
    • May need one extra node for final carry

  • Space: O(max(m, n))

    • Result list has max(m, n) + 1 nodes
    • Not counting output, O(1) extra space

Visual Example

For [2,4,3] + [5,6,4] (342 + 465 = 807):

Step 1: Add 2 + 5 = 7, carry = 0
  2 → 4 → 3
  5 → 6 → 4
  7

Step 2: Add 4 + 6 = 10, carry = 1
  2 → 4 → 3
  5 → 6 → 4
  7 → 0

Step 3: Add 3 + 4 + 1(carry) = 8, carry = 0
  2 → 4 → 3
  5 → 6 → 4
  7 → 0 → 8

Result: [7,0,8] represents 807

Edge Cases

  1. Different lengths: [9,9] + [1] → [0,0,1] (99 + 1 = 100)
  2. Final carry: [5] + [5] → [0,1] (5 + 5 = 10)
  3. All zeros: [0] + [0] → [0]
  4. Long carry chain: [9,9,9] + [1] → [0,0,0,1]

Solution

java
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11
12class Solution {
13    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
14        ListNode dummy = new ListNode(0);
15        ListNode curr = dummy;
16        int carry = 0;
17
18        while (l1 != null || l2 != null || carry != 0) {
19            // Get values (0 if list ended)
20            int val1 = (l1 != null) ? l1.val : 0;
21            int val2 = (l2 != null) ? l2.val : 0;
22
23            // Calculate sum and carry
24            int total = val1 + val2 + carry;
25            carry = total / 10;
26            int digit = total % 10;
27
28            // Create new node with digit
29            curr.next = new ListNode(digit);
30            curr = curr.next;
31
32            // Move to next nodes
33            if (l1 != null) l1 = l1.next;
34            if (l2 != null) l2 = l2.next;
35        }
36
37        return dummy.next;
38    }
39}
40
41
42// Alternative: Recursive Solution
43class SolutionRecursive {
44    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
45        return add(l1, l2, 0);
46    }
47
48    private ListNode add(ListNode l1, ListNode l2, int carry) {
49        if (l1 == null && l2 == null && carry == 0) {
50            return null;
51        }
52
53        int val1 = (l1 != null) ? l1.val : 0;
54        int val2 = (l2 != null) ? l2.val : 0;
55
56        int total = val1 + val2 + carry;
57        int digit = total % 10;
58        int newCarry = total / 10;
59
60        ListNode node = new ListNode(digit);
61        node.next = add(
62            (l1 != null) ? l1.next : null,
63            (l2 != null) ? l2.next : null,
64            newCarry
65        );
66
67        return node;
68    }
69}
70
Loading visualizer...