Convert Binary Number in Linked List to Integer — Bit Shift Accumulation

Problem Statement#

Given the head of a singly linked list where each node contains either 0 or 1, interpret the linked list as a binary number where the most significant bit is at the head. Return the integer value of this binary number.

Constraints:

• The linked list is not empty
• The number of nodes will not exceed 30
• Each node's value is either 0 or 1

Example 1:

Input:  head = [1, 0, 1]
Output: 5
Explanation: (101) in binary = 5 in decimal

Example 2:

Input:  head = [0]
Output: 0

Example 3:

Input:  head = [1, 1, 1, 1, 1]
Output: 31
Explanation: (11111) in binary = 31 in decimal

Why This Problem Matters#

Convert Binary Number in a Linked List to Integer (LeetCode 1290) combines two distinct skills: linked list traversal and binary number conversion. While it's rated Easy, it commonly appears in Amazon phone screens as a warm-up problem because it tests whether you understand both bit manipulation and pointer movement — two fundamental tools in systems programming.

The key insight is recognizing the standard binary-to-decimal conversion algorithm: process digits left-to-right, and for each new digit d, the new number is prev * 2 + d. The * 2 operation is identical to a left shift by 1 (<< 1). This is Horner's method applied to base-2 numbers.

This pattern extends to reading any base-N number from a sequence: replace << 1 with * N and | head.val with + digit. Understanding it in binary prepares you for problems like converting numbers from any arbitrary base, which appears in string-to-integer (atoi) problems.

For interviews, this problem tests conciseness. The optimal solution is a tight 3-line loop. If you write substantially more, you've overcomplicated it.

The Core Insight#

To convert a binary number digit-by-digit from left to right, maintain a running integer num. At each step:

1. Shift num left by 1 bit (equivalent to multiplying by 2) — this makes room for the new bit.
2. OR in the current bit (num | head.val) — this places the new bit in the least significant position.

Mathematically: num = (num << 1) | bit

For [1, 0, 1]:

• Start: num = 0
• After bit 1: (0 << 1) | 1 = 1 (binary: 1)
• After bit 0: (1 << 1) | 0 = 2 (binary: 10)
• After bit 1: (2 << 1) | 1 = 5 (binary: 101)

Result: 5.

Visual Dry Run#

Input: 1 -> 0 -> 1

Result: 5.

Verification: 1*4 + 0*2 + 1*1 = 5. Correct.

Solution (Optimal)#

Python#

def getDecimalValue(head):
    num = 0
    while head:
        num = (num << 1) | head.val  # shift left, OR in new bit
        head = head.next
    return num

Time complexity: O(n) — single pass through the list.

Space complexity: O(1) — only one integer variable.

JavaScript#

var getDecimalValue = function(head) {
    let num = 0;
    while (head !== null) {
        num = (num << 1) | head.val;  // left shift and OR
        head = head.next;
    }
    return num;
};

Alternative: accumulate with multiplication

def getDecimalValue(head):
    num = 0
    while head:
        num = num * 2 + head.val  # equivalent to (num << 1) | head.val
        head = head.next
    return num

Both are correct. The << 1 version is slightly more idiomatic for binary operations; the * 2 version is arguably more readable.

Complexity:

Common Mistakes#

1. Converting to a string first. Some candidates collect all bits into a string, then call int(s, 2). This works but uses O(n) space unnecessarily and shows you're not comfortable with bit operations. Use the accumulation pattern directly.

2. Using + instead of | for the new bit. num * 2 + head.val and (num << 1) | head.val are equivalent when head.val is 0 or 1. However, | is the semantically correct operation for setting a bit, and it's faster on most hardware.

3. Off-by-one in the shift. The shift happens before incorporating the new bit, not after. (num << 1) | bit is correct. (num | bit) << 1 would shift the last bit one position too far — giving the wrong result.

4. Not handling a single-node list. If the list is [0] or [1], the loop runs once: (0 << 1) | 0 = 0 or (0 << 1) | 1 = 1. Both are correct. No special case needed.

5. Integer overflow concern. The problem says at most 30 nodes, so the binary number fits in a 32-bit integer (max value is 2^30 - 1 = 1,073,741,823). In Python, integers are arbitrary precision, so no overflow. In JavaScript, << operator works on 32-bit integers — still safe for 30 bits.

Interview Tips#

1. Name the pattern: "This is Horner's method applied to base 2. Each step I shift left by one and OR in the new bit."

2. Show the mathematical equivalence: (num << 1) | bit == num * 2 + bit — explaining both forms shows depth.

3. Mention the constraint: "Since there are at most 30 nodes, the result fits in a 32-bit integer — no overflow concern."

4. Code speed: This is a 30-second problem. Aim for 3 lines of loop body and nothing else.

5. Extend it: "The same pattern handles any base-N number: replace << 1 with * N and | bit with + digit."

Follow-up Questions#

Q: How would you convert a decimal (base 10) number stored in a linked list? Replace (num << 1) | head.val with num * 10 + head.val. Same Horner's method in base 10.

Q: What if the linked list stores the number in reverse (LSB at head)? You'd need to reverse the list first (O(n) time, O(1) space), then apply the same algorithm. Alternatively, traverse the list to collect values, then process them in reverse — but that's O(n) space.

Q: What if there are leading zeros (e.g., [0, 0, 1, 0, 1])? Leading zeros are handled naturally — (0 << 1) | 0 = 0 — they just don't contribute to the value. Result would be 5 regardless.

Q: Can you do this recursively? Yes: def helper(node): return 0 if not node else (helper(node.next) + node.val * 2^depth). But you'd need to know the depth upfront or use two passes. The iterative approach is cleaner.

Q: How is this related to the "Add Binary" problem? Add Binary (LC 67) works on strings, not linked lists, but uses the same bit-by-bit addition with carry. The carry propagation pattern is analogous to the accumulation pattern here.

Key Takeaways#

• The accumulation pattern num = (num << 1) | bit is Horner's method in base 2 — left shift makes room for the new bit, OR inserts it.
• Time is O(n), space is O(1) — single pass, one integer variable.
• (num << 1) | bit and num * 2 + bit are equivalent for binary digits — both are acceptable in interviews.
• The shift-then-OR order matters: shift first, then OR. Reversing gives the wrong result.
• At most 30 nodes means no integer overflow in any standard language (32-bit integers hold values up to ~2 billion).
• The same pattern generalizes to any base: replace << 1 with * N for base-N number conversion.