The O(n) Club: Binary Linked List Conversion Without The Fuss

The O(n) Club: Binary Linked List Conversion Without The Fuss

⚡ TL;DR

Binary in a singly linked list (MSB at the head) goes to decimal. One pass, leftward shifts, and you’re done. Here’s how a non-zombie Java dev does it:

// Java: Dead simple, fast as coffee brewing
int total = 0;
for (ListNode node = head; node != null; node = node.next) {
    total = (total << 1) | node.val;
}
// 'total' is the answer. Take a break.

🧠 How Devs Usually Mess This Up

Everyone’s got baggage. Some folks see ‘linked list’ and panic, trying to reverse the thing or stash nodes in an array ‘just in case.’ Others read the bits backwards, treating head as the least significant bit. Pro tip: don’t! The spec always makes head your leftmost digit—think of it as your most responsible team lead. You don’t need a stack, and you definitely don’t need another coffee.

🔍 What’s Actually Going On

Imagine reading numbers on a vintage ticker tape—the old bank-heist kind. Every bit you read, your number doubles (shift left) and then you stick on the new bit at the end. Don’t overthink, just keep rolling. It’s like building a Lego tower where every brick added makes the whole thing twice as tall, then you slap a new bit on top. Simple, sturdy, no existential dread.

🛠️ PseudoCode

• Start with zero: result = 0
• Walk through each node:
  • Shift your result left: result << 1
  • OR/ADD in the node’s value: result = (result << 1) | node.val
  • Move to the next node
• Celebrate: No stacks, no regrets. Your decimal value is waiting.

If bitwise isn’t your jam: result = result * 2 + node.val does the job too. Same magic, less wizard hat.

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public class Solution {
    public int getDecimalValue(ListNode head) {
        int result = 0;
        while (head != null) {
            result = (result << 1) | head.val;
            head = head.next;
        }
        return result;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Wrong order, wrong answer: Processing right-to-left means you’re giving yourself bugs for (literally) no reason.
• Stash-itis: Using a stack, array, or anything else is just wasting cycles meant for Netflix.
• Single node? Relax: Input with only or 1 just returns itself. No tricky foot-guns here.
• Overflow-phobia: Unless you have 31+ nodes, Java’s int laughs this off. (Problem never lets you go that far anyway.)
• Big O(ops): O(n) time (just one loop!), O(1) space (unless you count coffee as storage).

🧠 Interviewer Brain-Tattoo

“If your solution needs more than one pass, or any extra containers, congrats—you’re making Linked Lists harder than LinkedIn.”