Add Two Numbers

PracticeNeetCode ↗LeetCode ↗

Two non-empty linked lists represent two non-negative integers, with digits stored in reverse order — one digit per node. Add the two numbers and return the sum as a linked list in the same reversed-digit format.

Example

Key Pointers

• Because digits are stored least-significant-first, you can add left to right exactly like manual addition, carrying as you go.
• A dummy head simplifies building the result list, same as merging two lists.
• Keep looping while either list still has nodes or there's a leftover carry — the two lists can be different lengths.

Step-by-Step Analysis

1. Create a dummy node, a tail pointer, and carry = 0.
2. While l1 or l2 or carry is truthy: sum the current digits (treating a run-out list as 0) plus carry.
3. New digit = total % 10, new carry = total // 10; append a node with that digit and advance tail, l1, l2.
4. Return dummy.next once both lists and the carry are exhausted.

Complexity

Time: O(max(n, m)) — Space: O(max(n, m)) for the output

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    tail = dummy
    carry = 0

    while l1 or l2 or carry:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0
        total = v1 + v2 + carry
        carry = total // 10
        tail.next = ListNode(total % 10)
        tail = tail.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

Code Explanation

How the solution above works, piece by piece.

1. The lists store numbers least-significant digit first, so walking forward is walking from the ones column up.
2. while l1 or l2 or carry: continue while either list has digits or a carry is left over (e.g. 5 + 5 needs an extra node for the final 1).
3. A missing digit counts as 0, so lists of different lengths just work.
4. carry = total // 10 and the new node gets total % 10.
5. The dummy head avoids a special case for the first digit. O(max(m, n)) time.

Visual Walkthrough

Running it on l1 = [2, 4, 3], l2 = [5, 6, 4] (342 + 465):

Video Explanation

NeetCode — Add Two Numbers, LeetCode 2