Convert Binary Number in a Linked List to Integer

easy linked list bit manipulation

Problem

Given the head of a singly linked list where each node holds a binary digit (0 or 1), the list represents a binary number with the most significant bit at the head. Return the integer value.

Inputhead = 1 → 0 → 1

Output5

Binary 101 is decimal 5. Walk left-to-right: 0, 1, 10 (=2), 101 (=5).

bits (0s and 1s, comma-separated)

def get_decimal_value(head):
    acc = 0
    node = head
    while node:
        acc = (acc << 1) | node.val
        node = node.next
    return acc

function getDecimalValue(head) {
  let acc = 0;
  for (let node = head; node; node = node.next) {
    acc = (acc << 1) | node.val;
  }
  return acc;
}

class Solution {
    public int getDecimalValue(ListNode head) {
        int acc = 0;
        for (ListNode node = head; node != null; node = node.next) {
            acc = (acc << 1) | node.val;
        }
        return acc;
    }
}

int getDecimalValue(ListNode* head) {
    int acc = 0;
    for (ListNode* node = head; node; node = node->next) {
        acc = (acc << 1) | node->val;
    }
    return acc;
}

Explanation

The list holds binary digits with the most significant bit at the head, and we want the integer value. The slick way is to build the number as we walk, using a shift-left and OR on a running accumulator.

Reading binary left-to-right, each new digit makes the existing value worth twice as much and then tacks on the new bit. Doubling is exactly a left shift, so acc = (acc << 1) | node.val shifts what we have over by one place and drops the next bit into the empty ones-position.

We start with acc = 0 and apply that one line for every node from head to tail. No need to know the list length in advance — the shifting naturally scales the earlier bits as more arrive.

Example: 1 → 0 → 1. Start acc=0. Bit 1: (0<<1)|1 = 1. Bit 0: (1<<1)|0 = 2. Bit 1: (2<<1)|1 = 5. So 101 in binary is 5.

Each node is touched once and only an integer is kept, so this is O(n) time with O(1) extra space.

Time: O(n) Space: O(1)