The O(n) Club: Add Two Numbers II: Making Linked Lists Add Like 80s Calculators

The O(n) Club: Add Two Numbers II—Making Linked Lists Add Like 80s Calculators

⚡ TL;DR

LeetCode 445 is here to ruin your autopilot! You’re asked to add two singly-linked lists digit-by-digit, with most significant digit first. If you try a brute-force approach, you’ll end up stuck: you can’t just go backward in a singly-linked list. So, channel your inner accountant—reverse both lists virtually using stacks, sum from right to left, and sprinkle some head insertions at the end:

Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
while (l2 != null) { s2.push(l2.val); l2 = l2.next; }
int carry = 0;
ListNode head = null;
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
    int sum = carry;
    if (!s1.isEmpty()) sum += s1.pop();
    if (!s2.isEmpty()) sum += s2.pop();
    ListNode node = new ListNode(sum % 10);
    node.next = head;
    head = node;
    carry = sum / 10;
}

🧠 How Devs Usually Mess This Up

Let’s be honest: you see ‘add two numbers’ and your finger instinctively types the LeetCode 2 solution—traverse, sum, reverse. But here’s the twist: now you have the most significant digit up front, just like a price tag (not a receipt). So if you pretend you can just add forward, you’re basically sending carries the wrong way—like mailing a letter to yourself, but in the past.

The biggest rookie mistakes? Mutating the lists to reverse them (that’s a paddlin’), or just ignoring those sneaky leftward carries. Both approaches will have your interviewer sighing audibly.

🔍 What’s Actually Going On

Picture this: adding two ginormous numbers that only reveal one digit at a time, from left to right. Unlike your friendly calculator, you can’t type the whole thing in, slap enter, and get an answer. You need to “rewind” the list—but since Java lists aren’t tapes, we use stacks for a little memory trickery. Push each digit onto a stack: now the top of the stack is your units digit! Pop, add, handle the carry, prep a new node, slap it on the head. It’s not magic, it’s just Last In, First Out saving the day.

🛠️ PseudoCode

• Traverse first input list l1 and push each digit onto s1.
  while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
• Traverse second list l2, push each digit onto s2.
• Make a variable carry = 0 and create head = null for the result.
• While s1 or s2 aren’t empty, or carry is nonzero:
  • Pop from each stack if possible, or use 0 otherwise.
  • Add the digits and the carry.
  • Create a new node with value sum % 10.
  • Insert it at the front (head) of your answer list.
  • Update carry to sum / 10.
• Return head (it’s still pointing at the most significant digit!).

💻 The Code

// Definition for singly-linked list.
class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  Stack<Integer> s1 = new Stack<>();
  Stack<Integer> s2 = new Stack<>();
  while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
  while (l2 != null) { s2.push(l2.val); l2 = l2.next; }
  int carry = 0;
  ListNode head = null;
  while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
    int sum = carry;
    if (!s1.isEmpty()) sum += s1.pop();
    if (!s2.isEmpty()) sum += s2.pop();
    ListNode node = new ListNode(sum % 10);
    node.next = head;
    head = node;
    carry = sum / 10;
  }
  return head;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgot a final carry? If your result needs a new-most-significant digit (think 999+1=1000), you must add a node for that lonely carry at the end.
• Variable list lengths? The stacks even the playing field—no need to pad, just pop 0 if a stack is empty.
• Input list mutation? Don’t reverse the original lists; LeetCode will glare, and you’ll fail hidden test cases.
• Space/Time: Every node and stack slot costs O(1) space, but you need O(m+n) for inputs. Runtime? Also O(m+n). Unless you invent a quantum stack, that’s ideal.

🧠 Interviewer Brain-Tattoo

“Sometimes the only way to add things the way you want is to stack your problems, then pop them off one by one. Just like my inbox.”