The O(n) Club: Add Two Numbers, Linked Lists, and That Sneaky Carry

The O(n) Club: Add Two Numbers, Linked Lists, and That Sneaky Carry

⚡ TL;DR

Two linked lists. Digits in reverse. Add ’em, digit by digit, handling that treacherous carry. Return a new linked list with the same upside-down vibe. Sounds easy, right? So does parallel parking in theory. Here’s it all boiled down in Java:

// Sum, carry, repeat. Java magic below:
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
    int sum = carry;
    if (l1 != null) { sum += l1.val; l1 = l1.next; }
    if (l2 != null) { sum += l2.val; l2 = l2.next; }
    carry = sum / 10;
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
}
return dummy.next;

🧠 How Devs Usually Mess This Up

If developers got frequent-flyer miles for missing the carry or tripping on list length, Hawaii would need more runways. Here’s what usually goes sideways:

• Dropped Carry Syndrome: Two 9s = 18, not 7 or mystical nonsense. If you ignore the carry, your sum belongs on a blooper reel.
• Equal Length Assumicide: Some lists are shorter. Pretend missing digits are zeros—don’t just give up and go home.
• Ghost Carry Finale: After both lists, you might need one last node for a final carry (looking at you, 5 + 5 = 10). Miss it and your interviewer will catch it.

🔍 What’s Actually Going On

Imagine a tired cashier punching in two receipts, one upside down, digit by digit. Every time their sum goes over 9, they scribble a mental “1” for next round—the classic carry. In Java, we can’t just add arrays. Linked lists force us to hold hands with every node, and sneakily pad shorter lists with zeroes in our head. The dummy node is your backstage pass to skip the awkward ‘first node’ dance—just build, then reveal the real list at the end.

🛠️ PseudoCode

• Create a dummy node as the start of your result list.
• Set a carry variable. (You’ll need it. Trust me.)
• While there are still digits (or a leftover carry):
  • Take each digit—or use 0 if the list is out of ammo.
  • Add them, plus carry, and compute the total.
  • carry = sum / 10 for the next round’s baggage.
  • Set curr.next to a new node with sum % 10.
  • Advance curr and the input lists if they’re still alive.
• Return dummy.next so nobody ever sees your dummy starter.

💻 The Code

// Node class for all your linked list dreams
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
     while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Null Lists: Handle them just like a disappointing dessert—pretend they’re zero, don’t panic.
• One List Is Longer: Keep going, pad with 0s as needed (mentally—don’t actually mutate the input, that’s mean).
• Final Carry Fumble: Don’t sprint for the finish before checking for a last carry. Bugs love a dramatic exit.
• Complexity Reality Check: Each digit gets love once. Runtime is O(n); space is minimal (okay, excluding the output list, Captain Literal).

🧠 Interviewer Brain-Tattoo

“Forget the carry, and the carry will not forget you.”
It’ll come back—right in your bug tracker.