Add Two Numbers
Walk both linked lists in parallel, summing with carry; allocate one output node per step.
3 min read
linked-list math
Problem#
Two non-negative integers are stored as linked lists with the LSB first. Return their sum as a linked list in the same form.
Examples#
[2,4,3] + [5,6,4]→[7,0,8](342 + 465 = 807).[0] + [0]→[0];[9,9,9,9,9,9,9] + [9,9,9,9]→[8,9,9,9,0,0,0,1].
Constraints#
1 <= length <= 100, digits0..9, no leading zeros (except 0 itself).
Approach#
Walk both lists with a carry. At each step add a + b + carry, the units digit becomes the new node, the tens digit is the new carry. Continue until both lists are exhausted and carry is 0.
Solution#
struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0), *cur = &dummy; int carry = 0; while (l1 || l2 || carry) { int s = carry; if (l1) { s += l1->val; l1 = l1->next; } if (l2) { s += l2->val; l2 = l2->next; } carry = s / 10; cur->next = new ListNode(s % 10); cur = cur->next; } return dummy.next; }};func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} cur := dummy carry := 0 for l1 != nil || l2 != nil || carry > 0 { s := carry if l1 != nil { s += l1.Val l1 = l1.Next } if l2 != nil { s += l2.Val l2 = l2.Next } carry = s / 10 cur.Next = &ListNode{Val: s % 10} cur = cur.Next } return dummy.Next}from typing import Optional
class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) cur = dummy carry = 0 while l1 or l2 or carry: s = carry if l1: s += l1.val l1 = l1.next if l2: s += l2.val l2 = l2.next carry, digit = divmod(s, 10) cur.next = ListNode(digit) cur = cur.next return dummy.nextvar addTwoNumbers = function(l1, l2) { const dummy = new ListNode(0); let cur = dummy; let carry = 0; while (l1 || l2 || carry) { let s = carry; if (l1) { s += l1.val; l1 = l1.next; } if (l2) { s += l2.val; l2 = l2.next; } carry = Math.floor(s / 10); cur.next = new ListNode(s % 10); cur = cur.next; } return dummy.next;};class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; int carry = 0; while (l1 != null || l2 != null || carry > 0) { int s = carry; if (l1 != null) { s += l1.val; l1 = l1.next; } if (l2 != null) { s += l2.val; l2 = l2.next; } carry = s / 10; cur.next = new ListNode(s % 10); cur = cur.next; } return dummy.next; }}function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { const dummy = new ListNode(0); let cur: ListNode = dummy; let carry = 0; while (l1 || l2 || carry) { let s = carry; if (l1) { s += l1.val; l1 = l1.next; } if (l2) { s += l2.val; l2 = l2.next; } carry = Math.floor(s / 10); cur.next = new ListNode(s % 10); cur = cur.next; } return dummy.next;}Editorial#
Storing digits LSB first means we can sweep left-to-right while still respecting carry direction — the algorithm matches schoolbook addition exactly. The dummy head avoids special-casing the first node.
Complexity#
- Time:
O(max(m, n)). - Space:
O(max(m, n))for the result list.
Concept revision#
Related#