Add Two Numbers LeetCode 2 Deep Dive

LeetCode 2 — Add Two Numbers — gives you two non-empty linked lists l1 and l2 representing two non-negative integers. Each node contains a single digit and the digits are stored in reverse order: the head of the list is the least significant digit. Your task is to add the two numbers and return the sum as a linked list in the same reverse-order format.

The classic example is 342 + 465 = 807. The number 342 is stored as the linked list 2 → 4 → 3 (least significant first), and 465 is stored as 5 → 6 → 4. Adding them produces 807, which is returned as 7 → 0 → 8. The reverse-order storage is not an obstacle — it is a feature, because it means the least significant digits align naturally at the heads of the two lists, which is exactly where addition with carry begins.

The constraints guarantee that neither list is empty and that no list has leading zeros except for the number zero itself, which is represented as a single node with value 0. The node values are between 0 and 9 inclusive. The number of nodes in each list can be between 1 and 100, so the numbers can be very large — far beyond what any 32-bit or 64-bit integer can represent. The linked-list representation is the only viable storage format for such large integers.

The core algorithm mirrors how you add numbers by hand: start from the rightmost (least significant) digit and work left, carrying any overflow to the next position. Because the digits are already stored least-significant-first, the heads of l1 and l2 are exactly where you start. Initialize a carry variable to 0. At each position, compute sum = l1.val + l2.val + carry. The result digit is sum % 10 and the new carry is sum // 10 (which is either 0 or 1).

Create a new ListNode with value sum % 10 and append it to the result list. Then advance both l1 and l2 to their next nodes. Continue while either list has remaining nodes or the carry is nonzero. The carry check in the loop condition ensures the algorithm handles the case where the final addition produces a carry beyond the length of both lists.

The time complexity is O(max(m, n)) where m and n are the lengths of the two lists, because you traverse both lists once. The space complexity is O(max(m, n)) for the new result list, which has at most max(m, n) + 1 nodes (the extra node for a final carry).

When the two lists have different lengths, one list runs out of digits before the other. The standard approach treats any missing node as having value 0. In practice this means: when advancing l1, if l1 is null use 0 for its contribution; similarly for l2. The while loop continues as long as l1 is not null, l2 is not null, or carry is nonzero — any of the three conditions keeps the loop alive.

This three-condition loop handles all combinations of lengths naturally and uniformly. If l1 is longer, the extra digits from l1 plus any carry are added with 0 from the exhausted l2. If l2 is longer, the reverse. If both exhaust simultaneously but there is still a carry, the loop continues one more iteration to append the carry as a final node. No special-casing is needed for any of these scenarios.

A clean way to write this in Python is: val1 = l1.val if l1 else 0 and val2 = l2.val if l2 else 0. Then advance with l1 = l1.next if l1 else None. In Java the equivalent is val1 = (l1 != null) ? l1.val : 0 with l1 = (l1 != null) ? l1.next : null. The ternary style keeps the main loop body compact and readable.

Building a linked list from scratch usually requires special-casing the head node: the first node must be assigned differently from all subsequent nodes. The dummy node pattern eliminates this special case. Create a dummy head node at the start — a sentinel node that is never part of the real answer. Maintain a current pointer that starts at dummy. To append a new node, set current.next = new ListNode(digit) and advance current = current.next.

When the loop finishes, the result list starts at dummy.next, not dummy itself. The dummy node simply holds the place so that the first real node can be appended via current.next without any if-statement to handle the head case. This pattern appears in nearly every linked list construction problem — merge two sorted lists, merge k sorted lists, remove nth node from end, and more.

The dummy node costs one extra allocation but saves branching complexity that would otherwise make the code harder to read and verify. In interviews, reaching for the dummy node pattern immediately when building a new linked list signals familiarity with linked list idioms.

One of the most common bugs in Add Two Numbers is forgetting to handle the carry that remains after both lists are exhausted. Consider adding 99 + 1: the lists are [9, 9] and [1]. At position 0: 9 + 1 + 0 = 10, digit = 0, carry = 1. At position 1: 9 + 0 + 1 = 10, digit = 0, carry = 1. Both lists are now exhausted. But carry is still 1. A final node with value 1 must be appended, giving the result [0, 0, 1] which represents 100.

The correct while loop condition is while l1 or l2 or carry. The carry term ensures the loop runs one final iteration when both lists are done but carry remains. An incorrect condition — while l1 or l2 — would exit the loop with carry = 1 still pending, returning [0, 0] instead of [0, 0, 1], giving 00 (i.e., 0) instead of 100.

This bug is subtle because it only manifests for inputs where the final column produces a carry — which requires digits that sum to 10 or more in the last position of the longer list. The test cases 342 + 465 = 807 and 0 + 0 = 0 will both pass with the wrong condition. Only inputs like 99 + 1, 999 + 1, or 9 + 1 will catch the bug. Always include the carry in the loop condition or add an explicit post-loop check.

Python implementation: def addTwoNumbers(self, l1, l2): dummy = ListNode(0); current = dummy; carry = 0; while l1 or l2 or carry: val1 = l1.val if l1 else 0; val2 = l2.val if l2 else 0; total = val1 + val2 + carry; carry = total // 10; current.next = ListNode(total % 10); current = current.next; l1 = l1.next if l1 else None; l2 = l2.next if l2 else None; return dummy.next. The single while loop with the three-condition OR handles all cases uniformly. Time O(max(m,n)), space O(max(m,n)) for the new list.

Java implementation: public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int val1 = (l1 != null) ? l1.val : 0; int val2 = (l2 != null) ? l2.val : 0; int total = val1 + val2 + carry; carry = total / 10; current.next = new ListNode(total % 10); current = current.next; l1 = (l1 != null) ? l1.next : null; l2 = (l2 != null) ? l2.next : null; } return dummy.next; } Java integer division truncates toward zero for positive numbers, so total / 10 is always 0 or 1 for single digits. The carry can never exceed 1 since the maximum sum per column is 9 + 9 + 1 = 19.

Both implementations use the same structure: dummy node, current pointer, carry variable, three-condition loop, ternary null-guards for exhausted lists. The result list has between max(m,n) and max(m,n)+1 nodes depending on whether the final column produces a carry. The +1 node case is exactly what 99 + 1 = 100 demonstrates with its extra leading-one node.

Multiply Strings — LeetCode 43 — is the multiplication analogue of Add Two Numbers. Rather than linked lists, it uses string representations of large integers and simulates long multiplication digit by digit. The carry propagation logic is identical in principle; the main difference is that multiplication produces partial products that must be accumulated across multiple positions. Solving Add Two Numbers first builds intuition for digit-level arithmetic that transfers directly to Multiply Strings.

Merge Two Sorted Lists — LeetCode 21 — uses the same dummy node pattern for list construction. Although the problem is list merging rather than arithmetic, the structural code — dummy head, current pointer, advance both pointers — is nearly identical to Add Two Numbers. The two problems share the same linked list construction skeleton; only the logic for choosing which node to append differs.

The linked list arithmetic family forms a cohesive problem cluster: Add Two Numbers (LeetCode 2) for digit-by-digit addition, Plus One (LeetCode 66) for array-based increment with carry, Multiply Strings (LeetCode 43) for multi-digit multiplication, and Add Binary (LeetCode 67) for binary string addition. Mastering the carry propagation pattern in any one of these problems gives you the core insight for all the others — only the base (decimal vs binary) and the representation (linked list vs array vs string) change.