Convert Binary Number in a Linked List to Integer

Easy Bit Manipulation Basics Original on LeetCode

Reported atNutanix

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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).
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.
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).