Problem statement

The head of a singly linked list is given, and every node holds a bit — 0 or 1. Read from head to tail, the bits spell a binary number with the most significant bit first.

Return the decimal value of that number.

Example 1

Input: head = [1,0,1]
Output: 5
Explanation: Binary 101 is 4 + 0 + 1 = 5.

Example 2

Input: head = [0]
Output: 0

Example 3

Input: head = [0,0,1,1,0]
Output: 6
Explanation: Leading zeros do not change the value: 00110 is 6.

Constraints

• The list is not empty
• The number of nodes does not exceed 30
• Each Node.val is 0 or 1

Hints for Convert Binary Number in a Linked List to Integer

1. Hint 1

   You do not know the length in advance, so you cannot know each bit's power of two up front.

2. Hint 2

   Reading a number left to right, each new digit shifts what you have one place to the left.

3. Hint 3

   Keep value = value * 2 + bit (or (value << 1) | bit) for each node.

How to solve Convert Binary Number in a Linked List to Integer

Horner's rule: reading a binary number from its most significant bit, each new bit doubles the value accumulated so far and adds itself. No length is needed.

Approach

1. Set value = 0.
2. For each node from head to tail: value = value * 2 + node.val.
3. Return value.

Why it works

After reading the bits b1 … bk, value equals the number they spell, because appending a bit b to a number x gives 2x + b. Induction over the list finishes the argument.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Starting from the tail with increasing powers requires the length or a reversal — unnecessary here.
• At most 30 bits keeps the value below 2^30, inside a 32-bit int.

Reference solution

Python

from typing import Optional

def getDecimalValue(head: Optional[ListNode]) -> int:
    value = 0
    while head:
        value = value * 2 + head.val
        head = head.next
    return value

Java

public static int getDecimalValue(ListNode head) {
    int value = 0;
    for (ListNode node = head; node != null; node = node.next) value = value * 2 + node.val;
    return value;
}

C++

int getDecimalValue(ListNode* head) {
    int value = 0;
    for (ListNode* node = head; node; node = node->next) value = value * 2 + node->val;
    return value;
}

JavaScript

var getDecimalValue = function(head) {
    var value = 0;
    for (var node = head; node !== null; node = node.next) value = value * 2 + node.val;
    return value;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Multiply Two Linked Lists Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy
• Valid Boomerang Easy