Add Two Numbers

Problem

Two non-negative integers are stored in linked lists with digits in reverse order (each node a single digit). Add them and return the sum as a linked list (also reverse-order).

Constraints

• 1 ≤ length ≤ 100
• 0 ≤ Node.val ≤ 9
• no leading zeros except 0 itself

Approach — Linked List

This is a Linked List problem. The idea: rework the list with careful pointer manipulation — often a dummy head and fast/slow pointers — in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) space.

Solution code

Python

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode()
        cur = dummy
        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, d = divmod(s, 10)
            cur.next = ListNode(d)
            cur = cur.next
        return dummy.next

Java

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 s = carry;
            if (l1 != null) { s += l1.val; l1 = l1.next; }
            if (l2 != null) { s += l2.val; l2 = l2.next; }
            carry = s / 10;
            tail.next = new ListNode(s % 10);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.