Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
A complete visual walkthrough of linked list digit-by-digit addition — from brute force to the elegant carry-forward solution.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Constraints:
[1, 100].0 <= Node.val <= 9The tempting approach: convert each linked list to an integer, add them, and convert back. Let's see it visually:
This fails for large numbers. Linked lists can have up to 100 nodes, meaning numbers up to 10100. That overflows every integer type — even long (max ~9.2 × 1018) and BigInteger adds unnecessary complexity. We need a solution that works digit by digit.
Remember how you added numbers by hand in school? Column by column, right to left, carrying the overflow. The linked lists are already in reverse order — the head is the ones digit. So we just walk both lists left to right, adding digits and tracking the carry!
At each position, compute sum = digit1 + digit2 + carry. The new digit is sum % 10, and the new carry is sum / 10.
Key idea: The reverse storage order is a gift, not an obstacle. It means the head of each list is the least significant digit — exactly where addition starts. No reversal needed!
Let's trace through the full algorithm with l1 = [2, 4, 3] and l2 = [5, 6, 4]. We use a dummy head node so we don't need special logic for the first node.
The dummy head trick: We create a placeholder node at the start so curr.next = new ListNode(digit) always works, even for the first real node. At the end, we return dummy.next to skip it.
The algorithm handles all edge cases naturally thanks to the while (l1 != null || l2 != null || carry != 0) condition:
When one list is shorter, we treat missing digits as 0.
The || carry != 0 part is crucial — it ensures we don't lose the final carry.
Works perfectly with one node each — just one iteration (plus one for carry if needed).
No special cases needed. The loop naturally handles all scenarios: when one list runs out (treat as 0), when both run out but carry remains (one more node), and when lists are the same length. The code stays clean and branch-free.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { this.val = val; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // Dummy head — avoids special-casing the first node ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; // Keep going while there are digits OR a leftover carry while (l1 != null || l2 != null || carry != 0) { // Start with the carry from the previous column int sum = carry; // Add l1's digit if it exists, then advance if (l1 != null) { sum += l1.val; l1 = l1.next; } // Add l2's digit if it exists, then advance if (l2 != null) { sum += l2.val; l2 = l2.next; } // Extract carry for the next column carry = sum / 10; // Create node with the ones digit of sum curr.next = new ListNode(sum % 10); curr = curr.next; } // Skip the dummy head return dummy.next; } }
// Definition for singly-linked list: // type ListNode struct { // Val int // Next *ListNode // } func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { // Dummy head — avoids special-casing the first node dummy := &ListNode{} curr := dummy carry := 0 // Keep going while there are digits OR a leftover carry for l1 != nil || l2 != nil || carry != 0 { // Start with the carry from the previous column sum := carry // Add l1's digit if it exists, then advance if l1 != nil { sum += l1.Val l1 = l1.Next } // Add l2's digit if it exists, then advance if l2 != nil { sum += l2.Val l2 = l2.Next } // Extract carry for the next column carry = sum / 10 // Create node with the ones digit of sum curr.Next = &ListNode{Val: sum % 10} curr = curr.Next } // Skip the dummy head return dummy.Next }
# Definition for singly-linked list. # class ListNode: # def __init__(self, val: int = 0, next: 'ListNode | None' = None): # self.val = val # self.next = next def add_two_numbers(l1: ListNode | None, l2: ListNode | None) -> ListNode | None: # Dummy head — avoids special-casing the first node dummy = ListNode(0) curr = dummy carry = 0 # Keep going while there are digits OR a leftover carry while l1 is not None or l2 is not None or carry != 0: # Start with the carry from the previous column total = carry # Add l1's digit if it exists, then advance if l1 is not None: total += l1.val l1 = l1.next # Add l2's digit if it exists, then advance if l2 is not None: total += l2.val l2 = l2.next # Extract carry for the next column carry = total // 10 # Create node with the ones digit of total curr.next = ListNode(total % 10) curr = curr.next # Skip the dummy head return dummy.next
// Definition for singly-linked list: // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>> } // impl ListNode { fn new(val: i32) -> Self { ListNode { next: None, val } } } impl Solution { pub fn add_two_numbers( mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { // Dummy head — avoids special-casing the first node let mut dummy = Box::new(ListNode::new(0)); let mut curr = &mut dummy; let mut carry = 0; // Keep going while there are digits OR a leftover carry while l1.is_some() || l2.is_some() || carry != 0 { // Start with the carry from the previous column let mut sum = carry; // Add l1's digit if it exists, then advance if let Some(node) = l1 { sum += node.val; l1 = node.next; } // Add l2's digit if it exists, then advance if let Some(node) = l2 { sum += node.val; l2 = node.next; } // Extract carry for the next column carry = sum / 10; // Create node with the ones digit of sum curr.next = Some(Box::new(ListNode::new(sum % 10))); curr = curr.next.as_mut().unwrap(); } // Skip the dummy head dummy.next } }
/** * Definition for singly-linked list. * class ListNode { * val: number; * next: ListNode | null; * constructor(val: number = 0, next: ListNode | null = null) { * this.val = val; this.next = next; * } * } */ function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { // Dummy head — avoids special-casing the first node const dummy = new ListNode(0); let curr = dummy; let carry = 0; // Keep going while there are digits OR a leftover carry while (l1 !== null || l2 !== null || carry !== 0) { // Start with the carry from the previous column let sum = carry; // Add l1's digit if it exists, then advance if (l1 !== null) { sum += l1.val; l1 = l1.next; } // Add l2's digit if it exists, then advance if (l2 !== null) { sum += l2.val; l2 = l2.next; } // Extract carry for the next column carry = Math.floor(sum / 10); // Create node with the ones digit of sum curr.next = new ListNode(sum % 10); curr = curr.next; } // Skip the dummy head return dummy.next; }
Enter two numbers as comma-separated digits in reverse order (ones digit first). Step through the addition to see carries and the result list being built.
We traverse both linked lists in a single pass, processing one node per iteration. The loop runs for max(m, n) iterations (plus one extra if a final carry exists), and each iteration does O(1) work: one addition, one modulo, one division, and one node allocation. The result list contains at most max(m, n) + 1 nodes, so the output space is also O(max(m, n)).
Traverses each list once to build the integer string, then performs one addition and one conversion back. Each traversal is O(m) or O(n). The intermediate integer requires O(max(m, n)) digits of storage, and it fails entirely for lists longer than ~18 nodes due to integer overflow.
A single while loop walks both lists in lockstep. Each iteration does O(1) work: one addition, one modulo, one division, and one node allocation. The output list has at most max(m, n) + 1 nodes (the extra node covers a final carry). Works for arbitrarily long lists with no overflow risk.
This is provably optimal: We must read every digit in both inputs, so O(max(m, n)) time is a lower bound. The output itself requires O(max(m, n)) space. The carry propagation at each step is O(1) — it never cascades — so there is no hidden cost. Both approaches share the same big-O, but digit-by-digit addition handles lists of any length without integer overflow.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.