Add two numbers represented by linked lists

Medium

Problem

Two non-negative numbers are stored as linked lists, one digit per node. Return their sum as a linked list in the same format. Confirm the digit order: LeetCode stores the digits in reverse (least significant first), GfG stores them most significant first.

Example 1

Input:  2 → 4 → 3 + 5 → 6 → 4 (reverse order)
Output: 7 → 0 → 8

342 + 465 = 807.

Also asked as: Add two numbers represented by linked lists

Test cases

Case 1

Input:    [2,4,3], [5,6,4]
Expected: [7,0,8]

Case 2

Input:    [0], [0]
Expected: [0]

Case 3

Input:    [9,9,9,9,9,9,9], [9,9,9,9]
Expected: [8,9,9,9,0,0,0,1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Digit-by-digit with carry (least-significant first)

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

If digits are stored LSB-first, walk both lists adding with carry into a new list. (MSB-first: reverse both, or use two stacks.)

function addTwoNumbers(a, b) {
const dummy = { val: 0, next: null };
let tail = dummy, carry = 0;
while (a || b || carry) {
const sum = (a?.val || 0) + (b?.val || 0) + carry;
carry = sum >= 10 ? 1 : 0;
tail.next = { val: sum % 10, next: null };
tail = tail.next;
a = a?.next; b = b?.next;
}
return dummy.next;
}