Start practising

Convert Binary Number in a Linked List to Integer

Easy Bit Manipulation Basics Original on LeetCode

Convert Binary Number in a Linked List to Integer is a easy bit manipulation problem solved with the basics pattern. The best approach, optimal (shift and or while walking), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from collect, then weight by position up.

Problem

A linked list holds the bits of a binary number, most significant bit first. Return the number’s decimal value.

Examples

Example 1

Input
head = [1, 0, 1]
Output
5

Example 2

Input
head = [0]
Output
0

Constraints

  • The list has 1 to 30 nodes; each node is 0 or 1; the most significant bit comes first.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Collect, then weight by positionO(n)O(n)
Optimal (shift and OR while walking)O(n)O(1)

1Collect, then weight by position

TimeO(n)
SpaceO(n)

Store the bits, then add bit · 2^(position from the end).

  1. Copy to a list; sum bits[i] << (n - 1 - i).
Java
class Solution {
    public int getDecimalValue(ListNode head) {
        List<Integer> bits = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) bits.add(p.val);
        int value = 0, n = bits.size();
        for (int i = 0; i < n; i++) value += bits.get(i) << (n - 1 - i);
        return value;
    }
}

2Optimal (shift and OR while walking)

TimeO(n)
SpaceO(1)

Each new bit shifts the value so far one place left, then fills the new lowest bit.

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

Edge cases to test

  • Leading zeros
  • 30 bits (still fits in an int)

Hints

Hint 1

Reading bits left to right: value = value · 2 + bit, i.e. (value << 1) | bit.

FAQ

What is the best time complexity for Convert Binary Number in a Linked List to Integer?

Optimal (shift and OR while walking) runs in O(n) time and O(1) extra space.

Which pattern does Convert Binary Number in a Linked List to Integer use?

It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, K-th Bit is Set or Not, Odd or Even.

Is there a brute force solution for Convert Binary Number in a Linked List to Integer?

Yes. Collect, then weight by position takes O(n) time and O(n) space. Store the bits, then add bit · 2^(position from the end).

Which edge cases should I test for Convert Binary Number in a Linked List to Integer?

Leading zeros; 30 bits (still fits in an int).