Add two numbers represented by linked lists
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]
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;}