Coding interview problems › Linked Lists

🔗 Linked Lists Medium

Add Two Numbers (Linked Lists)

Add two numbers stored as reversed linked lists: walk both lists together, add digit by digit and carry, like school addition. Tested Python and a live visual.

Also searched as: add two numbers represented by linked lists · sum of two linked lists with carry · linked list addition

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Use the linked list lab to practise walking and re-linking nodes one step at a time; here you walk two lists in lock-step and append to a third.

Open the playground →

The problem

Two non-negative integers are stored as linked lists of digits in reverse order, so 342 is 2 -> 4 -> 3. Return their sum as a linked list in the same reverse-digit form. Neither number has leading zeros except the number 0 itself.

Input2 -> 4 -> 3 and 5 -> 6 -> 4
Output7 -> 0 -> 8

342 + 465 = 807

Input9 -> 9 and 1
Output0 -> 0 -> 1

99 + 1 = 100: the final carry creates a new node.

The key insight

Reverse order is a gift: the lists start at the ones digit, exactly where column addition starts. Walk both lists together, add the two digits plus the carry, write total % 10 into a new node and carry total // 10 to the next column. Keep going while either list or the carry remains.

Brute force first: Converting each list to a Python integer, adding, and converting back works in Python, but fails in languages with fixed-size integers and skips the carry logic the question is about.

Step-by-step approach

  1. Create a dummy head, a tail pointer and carry = 0.
  2. Loop while a, b or carry is non-zero.
  3. Add carry plus the current digit of each list (0 if that list has ended).
  4. Append a node with total % 10 and set carry = total // 10.
  5. Advance whichever lists still have nodes. Return dummy.next.

Python solution

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


def add_two_numbers(a, b):
    dummy = tail = ListNode()
    carry = 0
    while a or b or carry:
        total = carry
        if a:
            total += a.val
            a = a.next
        if b:
            total += b.val
            b = b.next
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next

Complexity

TimeO(max(m, n))
SpaceO(max(m, n))

The loop runs once per digit of the longer number, plus at most one extra step for a final carry. The output list itself has up to max(m, n) + 1 nodes.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(max(m, n)) time for one pass over the longer list, and O(max(m, n)) space for the new result list.

What if the digits are stored in normal (most significant first) order?

Either reverse both lists first and reuse this solution, or push the digits of each list onto two stacks and pop them to add from the ones digit, building the result from the front.

Why not convert to integers and add?

It works in Python because integers have unlimited size, but interviewers want the digit-and-carry loop, which works in any language and for numbers with thousands of digits.

Can the carry ever be more than 1?

No. Two digits plus a carry is at most 9 + 9 + 1 = 19, so the carry is always 0 or 1.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.