Two non-negative numbers are stored as linked lists with their digits in reverse order (least-significant digit first). Add them and return the sum as a linked list in the same reversed-digit form.
addLists(a, b)
Input format: listA | listB, each a list of single digits (reversed). For example
2 4 3 represents 342.
(2 4 3) + (5 6 4) // 342 + 465 = 807 → 7 0 8
(0) + (0) // → 0
(9 9) + (1) // 99 + 1 = 100 → 0 0 1
This is elementary-school column addition, represented as linked lists — and the reversed digit order isn't arbitrary, it's what makes this tractable. Adding by hand starts at the ones digit and works leftward, carrying when a column hits 10 or more. Storing the least-significant digit first means each list's head is exactly the digit to start from — no reversing needed.
99 + 1 = 100).Appending computed digits onto a growing result list has the same "first node is special" problem as building any list from scratch. A dummy anchor node with a tracked tail pointer sidesteps it — the same technique used whenever a list is built incrementally.
Since digits are stored least-significant-first, the list's natural head-to-tail order matches the natural addition order. A single synchronized walk carrying one small piece of state (the carry) is enough — no converting to numbers, no reversing, no lookahead. Each node is visited once; the result is proportional to the longer input (plus maybe one extra digit) — O(n) time and space.
def add_lists(a, b):
dummy = ListNode(0)
tail = dummy
carry = 0
while a is not None or b is not None or carry > 0:
total = carry
if a is not None:
total += a.val
a = a.next
if b is not None:
total += b.val
b = b.next
tail.next = ListNode(total % 10)
tail = tail.next
carry = total // 10
return dummy.next
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.