LeetCode 2 · Medium · Linked List

Add Two Numbers

Two non-negative numbers are stored as linked lists of digits, ones digit first. Return their sum as a linked list in the same reversed form.

O(max(m,n))time
O(1)extra space
carryschoolbook addition

digits ones-first · 1–7 digits each, 0 to 9 · no trailing 0 unless the number is 0

Digit lists ones digit on the left · each column is one place value · dashed = dummy · slash = null

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(); ListNode cur = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int v1 = l1 != null ? l1.val : 0; int v2 = l2 != null ? l2.val : 0; int val = v1 + v2 + carry; carry = val / 10; val = val % 10; cur.next = new ListNode(val); cur = cur.next; l1 = l1 != null ? l1.next : null; l2 = l2 != null ? l2.next : null; } return dummy.next;}
v1 + v2 + carry
—
carry
0
l1 · l2
—
result
—

Why it works

  1. Brute force converts: read each list into an integer, add, and split the sum back into digits. It breaks as soon as a list is longer than about 18 digits, because even long overflows, and it still needs a list for the answer.
  2. Reversed digits are a gift: the head is the ones digit, so walking the lists front to back is exactly how you add on paper, right to left, carrying into the next column.
  3. One pass over the longer list: each column costs O(1), so O(max(m, n)) time. Apart from the answer's own nodes, only carry and a few pointers: O(1) extra space.
  4. Pitfall: the last carry. 5 + 5 = 10 needs a node that neither input has. or carry in the loop condition creates it; without it the answer loses its leading 1.
  5. Pitfall: lists of different lengths. A finished list contributes 0 (l1 != null ? l1.val : 0) and its pointer stays null, so the loop keeps going on the longer one.
  6. Follow-up, Add Two Numbers II (445): digits come most significant first. Push both lists on stacks (or reverse them) to add from the ones place.