Command Palette

Search for a command to run...

Hectal
Problem 8.6 · Linked ListsMedium

Add Two Numbers

PatternDummy Head and Merging

What it teaches: Grade-school addition on linked lists: walk both lists, carry the tens digit, and build the result behind a dummy head.

Practise it on judges as “Add Two Numbers”.

The problem

Two non-negative integers are stored as linked lists with digits in reverse order (ones digit first). Add them and return the sum as a list in the same format.

Example 1

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]

342 + 465 = 807.

Example 2

Input: l1 = [9, 9, 9, 9], l2 = [9, 9]
Output: [8, 9, 0, 0, 1]

9999 + 99 = 10098.

Constraints

  • 1 ≤ nodes ≤ 100 per list
  • 0 ≤ digit ≤ 9
  • No leading zeros except the number 0

Pattern clues in the wording

  • → Digits in reverse order = addition from the ones place
  • → Lists of different lengths and a final carry

These clues point to Dummy Head and Merging: Start with a fake node before the real head so building, merging and deleting never need special cases for the first node.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        int carry = 0;
        return dummy.next;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
l1 = [2,4,3]
l2 = [5,6,4]
[7,0,8]
2
l1 = [0]
l2 = [0]
[0]
3
l1 = [9,9,9,9]
l2 = [9,9]
[8,9,0,0,1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: digit-by-digit with a carry · O(max(n, m))
1

Optimal: digit-by-digit with a carry

Time O(max(n, m)) Space O(max(n, m)) for the result

Loop while either list has nodes or carry > 0. Sum = digits (0 if a list is done) + carry. Append sum % 10; carry = sum / 10.

Approach 1
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

Verdict: Handles different lengths and the final carry in one loop.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Different lengths
  • A final carry (999 + 1)
  • Both are 0

Mistakes people make

  • Converting to int or long first: 100 digits overflow any primitive.
  • Stopping when both lists end but a carry remains.

Interview

Follow-up questions

What if digits are stored most significant first?