Skip to main content

2. Add Two Numbers

medium

Add two non-negative integers represented as linked lists of digits in reverse order. Tests careful carry handling and the dummy-head pattern under variable-length inputs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Constraints

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Examples

Example 1

Input
l1 = [2,4,3], l2 = [5,6,4]
Output
[7,0,8]

Explanation: 342 + 465 = 807.

Example 2

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

Example 3

Input
l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output
[8,9,9,9,0,0,0,1]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk both lists in lockstep, summing aligned digits.

Hint 2

Maintain a carry. At each step the new digit is (a + b + carry) % 10; the new carry is (a + b + carry) / 10.

Hint 3

Don't forget the leftover carry after the last node — it might need a brand-new node.

Solution approach

Reveal approach

Dummy-head accumulation. Walk both lists with two pointers and a carry variable initialized to 0. Loop while either pointer is non-null OR carry > 0: sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry; carry = sum / 10; append new node with sum % 10 to tail; advance whichever pointers are non-null. After the loop return dummy.next. The single loop condition (including the carry check) elegantly handles the trailing-carry case where you need to create a new leading digit. O(max(n, m)) time, O(max(n, m)) space for the output.

Complexity

Time
O(max(n, m))
Space
O(max(n, m))

Related patterns

  • linked-list
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Add Two Numbers and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →