Add Two Numbers Stored in Reverse Order

You're given two non-empty linked lists, l1 and l2, each representing a non-negative integer with its digits stored in reverse order — the head node holds the ones digit. Add the two numbers and return the sum as a linked list in the same reverse-order format. Because the least significant digit already comes first in both lists, this maps almost directly onto how addition works by hand: process one digit position at a time, track a carry for anything that overflows past 9, and keep going until both lists — and the carry — are exhausted.

Test Case 1:

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

Output:[7, 0, 8]

Explanation:342 + 465 = 807, stored back in reverse order.

Test Case 2:

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

Output:[0]

Explanation:0 + 0 = 0.

Test Case 3:

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

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

Explanation:9999999 + 9999 = 10009998 — the result list is a digit longer than either input.

Constraints

◆1 ≤ number of nodes in l1, l2 ≤ 100
◆0 ≤ node value ≤ 9
◆Each list represents a non-negative integer with digits stored in reverse order — the head is the ones digit — and has no leading zeros, except the number 0 itself

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

l1 (digits, least significant first) — 1-6 digitsl2 (digits, least significant first) — 1-6 digits

1	class Solution {
2	public Node addTwoNumbers(Node l1, Node l2) {
3	Node dummy = new Node(0);
4	Node tail = dummy;
5	int carry = 0;
6	while (l1 != null \|\| l2 != null \|\| carry > 0) {
7	int x = (l1 != null) ? l1.val : 0;
8	int y = (l2 != null) ? l2.val : 0;
9	int sum = x + y + carry;
10	carry = sum / 10;
11	tail.next = new Node(sum % 10);
12	tail = tail.next;
13	if (l1 != null) l1 = l1.next;
14	if (l2 != null) l2 = l2.next;
15	}
16	return dummy.next;
17	}
18	}
19

Linked List

2

l1

4

3

null

Linked List

5

l2

6

4

null

Linked List

null

Variables

taildummy

carry0

INITIALIZE

A dummy node lets the first digit attach the same way as every later one. carry starts at 0.

Step 1 / 18

Approach & Solutions

Brute Force — Convert Each List to a Number, Add, Rebuild the Result

Good

Since each list already stores its digits least-significant-first, walk each list once, multiplying by an increasing power of 10 to reconstruct the actual number it represents. Add the two numbers normally, then peel the sum apart one digit at a time (also least-significant-first, via % 10 and / 10) to build the result list — which conveniently comes out in the same reverse order the problem wants, with no extra reversal needed.

TimeO(n + m)

SpaceO(1)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node addTwoNumbers(Node l1, Node l2) {
        long num1 = 0, mult1 = 1;
        while (l1 != null) {
            num1 += l1.val * mult1;
            mult1 *= 10;
            l1 = l1.next;
        }
        long num2 = 0, mult2 = 1;
        while (l2 != null) {
            num2 += l2.val * mult2;
            mult2 *= 10;
            l2 = l2.next;
        }
        long sum = num1 + num2;
        Node dummy = new Node(0);
        Node tail = dummy;
        if (sum == 0) {
            tail.next = new Node(0);
            tail = tail.next;
        }
        while (sum > 0) {
            tail.next = new Node((int) (sum % 10));
            tail = tail.next;
            sum /= 10;
        }
        return dummy.next;
    }
}

Optimal — Single Pass With Carry, Build the Result as You Go

Optimal

Walk l1 and l2 side by side, one node at a time. At each step, add whichever values exist (0 if a list has run out) plus the carry from last time, and append a single new digit node to the result. Keep going as long as either list still has nodes, or a carry is still pending. No number ever gets reconstructed — the addition happens node by node, exactly like adding by hand.

TimeO(max(n, m))

SpaceO(max(n, m))

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

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

Constraints

Try the Dry Run

Approach & Solutions

Brute Force — Convert Each List to a Number, Add, Rebuild the Result

Optimal — Single Pass With Carry, Build the Result as You Go

Related Problems