linkjobai

Convert Binary Number in a Linked List to Integer (LeetCode 1290): Shift as You Go

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 0 returns 0.
  • Leading zeros are fine: 0 -> 0 -> 1 is 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.)