Binary Chain to Number
EasyLinked List
Problem
A serial device sends a number one bit at a time, most significant bit first, and the driver stores the bits in a singly linked list.
Given the head of that list (every value is 0 or 1), return the number it represents in decimal.
Example 1
- Input:
- head = [1, 0, 1, 1]
- Output:
- 11
Binary 1011 is 8 + 2 + 1 = 11.
Example 2
- Input:
- head = [0]
- Output:
- 0
Constraints
- 1 ≤ number of nodes ≤ 30
- node.val is 0 or 1
Hint
Show the first hint
You do not know the length in advance, so you cannot know the weight of the first bit yet. Does that matter?
Walkthrough
How to approach it
01Clarify before coding
- Which end is the most significant bit? The head.
- Can there be leading zeros? Yes, like [0, 0, 1, 0]; they do not change the value.
- Can the result overflow? No, at most 30 bits fits in a 32-bit signed integer.
02Brute force
Walk once to find the length n, then walk again adding bit · 2^(n - 1 - i) for each position i.
Cost: O(n) time and O(1) space, but two passes and explicit powers; it can be done in one.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.