The problem: a singly linked list holds 0s and 1s, most significant bit first. Return the decimal value. Example: 1 -> 0 -> 1 is 5.
The one-pass answer
def getDecimalValue(head): val = 0 while head: val = (val << 1) | head.val head = head.next return val
Each new bit doubles everything read so far and adds itself. This is Horner's rule, the same idea used to parse a decimal string (val = val * 10 + digit). O(n) time, O(1) space, one pass, no need to know the length first.
The tempting two-pass answer
Some candidates first count the length L, then add bit * 2^(L-1-i). It works but takes two passes and needs care with exponents. Mention it only to explain why the shift version is better.
Edge cases to say out loud
- A single node
0returns 0. - Leading zeros are fine:
0 -> 0 -> 1is 1. - Overflow: the problem caps the list at 30 nodes, so a 32-bit int is safe. If the list were longer, use a big integer or return the value modulo some number, applying the modulo after each step.
Variants
- Least significant bit first. Then keep a running power:
val += bit * p; p <<= 1. - Return the string instead. Collect bits and join, or skip the list entirely.
- Add two binary lists. Reverse or use stacks, then carry, just like Add Two Numbers.
Takeaway
Recognise Horner's rule, explain why it avoids a length pass, and cover overflow before you are asked.
From the team at Linkjob, which builds an interview assistant for live coding rounds. (Disclosure: affiliated.)