LeetCode · #2

Add Two Numbers Solution

Given two non-empty linked lists representing non-negative integers in reverse order, return their sum as a linked list.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #2

🏗️

Pattern

Math — digit-by-digit with carry

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

Example

 Input: l1 = 2→4→3 (342)
        l2 = 5→6→4 (465)
Output: 7→0→8 (807)
// 342 + 465 = 807 

Constraints

 • 1 ≤ number of nodes ≤ 100 • 0 ≤ Node.val ≤ 9 • No leading zeros (except the number 0 itself) 

Section Two · Approach 1

Convert to Integer — Overflow risk

Convert both lists to integers, add, then convert the result back to a list. Simple but fails for numbers exceeding integer range (up to 100 digits!).

Problem: 100-digit numbers overflow any integer type. The digit-by-digit approach handles arbitrarily long numbers naturally, just like manual addition on paper.

Section Three · Approach 2

Digit-by-Digit Addition — O(max(m, n))

Add corresponding digits from both lists plus the carry. Store the ones digit in a new node, propagate the tens digit as carry. Continue until both lists and carry are exhausted.

💡 Mental model: Elementary school long addition. Start from the rightmost digit (which is conveniently the head, since digits are reversed). Add two digits + carry. Write down the ones place, carry the tens place. Move left. This is exactly what we're doing node by node.

Algorithm

Step 1: Create a dummy node and a tail pointer. carry = 0.
Step 2: While l1 or l2 or carry > 0:
Sum = (l1.val or 0) + (l2.val or 0) + carry.
carry = sum / 10. digit = sum % 10.
Create new node with digit, link it.
Advance l1, l2 if not null.
Step 3: Return dummy.next.

🎯 Why reverse order helps:

Digits are stored least-significant first — exactly the order we need for addition. No reversal required.
We start adding from the ones place naturally.

Section Four · Trace

Visual Walkthrough

Trace: l1 = 2→4→3, l2 = 5→6→4:

Digit-by-digit addition with carry

Section Five · Implementation

Code — Java & Python

Java — Digit-by-digit

 class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode 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; }

            carry = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
return dummy.next;
    }
}

Python — Digit-by-digit

 class Solution:
def addTwoNumbers(self, l1, l2):
        dummy = tail = ListNode(0)
        carry = 0 while l1 or l2 or carry:
            s = carry
if l1: s += l1.val; l1 = l1.next
if l2: s += l2.val; l2 = l2.next

            carry, digit = divmod(s, 10)
            tail.next = ListNode(digit)
            tail = tail.next
return dummy.next

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Digit-by-digit ← optimal	O(max(m,n))	O(max(m,n))	One pass, handles any length. Space for output list.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Different lengths	`9→9→9 + 9→9`	Shorter list runs out first — treat missing digits as 0.
Final carry	`9→9 + 1` = 0→0→1	Result is longer than both inputs. The `\|\| carry` condition handles this.
Zero	`0 + 0`	0+0+0=0, carry=0 → single node [0].

⚠ Common Mistake: Forgetting to check carry != 0 in the loop condition. If both lists end but carry is 1 (e.g., 99+1=100), you miss the leading 1. Always include carry in the termination condition.

← Back to Linked List problems

LearningTree

LC 2 · Add Two Numbers — Solution & Explanation | DSA Guide