LeetCode 1290 - Convert Binary Number in a Linked List to Integer

Difficulty: 🟢 Easy
Topics: Linked List, Math

Solution

Problem Understanding

The problem gives us the head of a singly linked list where every node contains either 0 or 1. These values together represent a binary number. The head of the list stores the most significant bit, meaning the binary digits appear in the same order that we normally write binary numbers from left to right.

Our task is to convert this binary representation into its decimal integer equivalent and return that value.

For example, if the linked list is:

1 -> 0 -> 1

then the binary number is 101₂, which equals 5 in decimal.

The input is not an array or string, it is a linked list. That means we cannot directly index into positions, and we must traverse node by node.

The constraints are very small:

The linked list is guaranteed to be non-empty.
The number of nodes is at most 30.
Each node value is either 0 or 1.

These constraints tell us several important things:

The resulting integer will safely fit inside a standard 32-bit integer.
Even less efficient solutions would still pass because the input size is tiny.
However, the goal is still to design a clean and optimal linear-time solution.

There are several edge cases worth considering:

A list containing only one node, such as [0] or [1]
A binary number with leading zeros, such as [0,0,1]
A list where every value is 1
The maximum-length input of 30 nodes

The problem guarantees that the list is valid binary input, so we never need to handle invalid digits.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to first extract all bits from the linked list into an array or string. After that, we can process the binary representation from right to left and compute the decimal value using powers of two.

For example:

1 -> 0 -> 1

could become:

"101"

We would then evaluate:

1 × 2² + 0 × 2¹ + 1 × 2⁰ = 5

This works because binary positional notation defines each digit as a power of two based on its position.

Although this approach is correct, it requires extra memory to store the bits separately. It also performs additional work computing powers or reversing positions.

Optimal Approach

The key observation is that binary numbers can be built incrementally while traversing the linked list.

Suppose we have already processed some bits and currently hold their decimal value in a variable called result.

When we read the next binary digit:

shifting left by one position in binary is equivalent to multiplying by 2
then we add the new bit

So the update rule becomes:

result = result * 2 + current_bit

or equivalently using bit manipulation:

result = (result << 1) | current_bit

This mirrors how binary numbers are naturally constructed digit by digit.

For example:

1 -> 0 -> 1

Processing step by step:

0
0 * 2 + 1 = 1
1 * 2 + 0 = 2
2 * 2 + 1 = 5

This approach processes the list in one pass and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Store bits separately, then evaluate binary value
Optimal	O(n)	O(1)	Build decimal value incrementally during traversal

Algorithm Walkthrough

Initialize a variable called result to 0.

This variable will store the decimal value constructed so far. 2. Start traversing the linked list from the head node.

Since the linked list represents the binary number from most significant bit to least significant bit, we process nodes in order. 3. For each node, shift the current result left by one bit.

Shifting left by one position is equivalent to multiplying the current value by 2. This creates room for the next binary digit. 4. Add the current node's value.

Because each node contains either 0 or 1, appending the next binary digit is simply adding that bit. 5. Move to the next node and repeat until the traversal is complete. 6. Return the final value stored in result.

Why it works

At every step, result represents the decimal value of all binary digits processed so far. Multiplying by 2 shifts the existing binary digits left by one position, exactly matching binary positional rules. Adding the current bit appends the new binary digit to the number. Since every node is processed in order from most significant to least significant bit, the final value is the correct decimal representation.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def getDecimalValue(self, head: Optional[ListNode]) -> int:
        result = 0
        current = head

        while current:
            result = (result << 1) | current.val
            current = current.next

        return result

The implementation begins by initializing result to 0. This variable stores the decimal value being built during traversal.

We then iterate through the linked list using a pointer named current.

Inside the loop, the expression:

result = (result << 1) | current.val

performs two operations:

result << 1 shifts the current binary number left by one bit, equivalent to multiplying by 2
| current.val appends the current binary digit

Because each node contains only 0 or 1, the bitwise OR operation cleanly inserts the new bit into the least significant position.

After processing the current node, we advance to the next node until the traversal finishes.

Finally, we return the completed decimal value.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getDecimalValue(head *ListNode) int {
    result := 0
    current := head

    for current != nil {
        result = (result << 1) | current.Val
        current = current.Next
    }

    return result
}

The Go implementation follows exactly the same logic as the Python solution. The main language-specific difference is that Go uses nil instead of None for linked list termination checks.

The bit manipulation operations work identically in Go. Since the input size is limited to 30 bits, integer overflow is not a concern for Go's standard integer type.

Worked Examples

Example 1

Input:

[1,0,1]

Binary representation:

101₂

Step	Current Bit	Result Before	Result After
Start	-	0	0
1	1	0	1
2	0	1	2
3	1	2	5

Detailed computation:

Start with result = 0
Process 1

(0 << 1) | 1 = 1

Process 0

(1 << 1) | 0 = 2

Process 1

(2 << 1) | 1 = 5

Final answer:

Example 2

Input:

[0]

Binary representation:

0₂

Step	Current Bit	Result Before	Result After
Start	-	0	0
1	0	0	0

Detailed computation:

Start with result = 0
Process 0

(0 << 1) | 0 = 0

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single traversal of the linked list, so the running time grows linearly with the number of nodes.

No additional data structures proportional to the input size are allocated. The algorithm only maintains a running integer value and a traversal pointer, so the extra space usage is constant.

Test Cases

# Helper class for testing
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

assert solution.getDecimalValue(build_list([1, 0, 1])) == 5  # basic example
assert solution.getDecimalValue(build_list([0])) == 0  # single zero
assert solution.getDecimalValue(build_list([1])) == 1  # single one
assert solution.getDecimalValue(build_list([1, 1, 1])) == 7  # all ones
assert solution.getDecimalValue(build_list([0, 0, 1])) == 1  # leading zeros
assert solution.getDecimalValue(build_list([1, 0, 0, 0])) == 8  # power of two
assert solution.getDecimalValue(build_list([1, 1, 0, 1])) == 13  # mixed bits
assert solution.getDecimalValue(build_list([0, 0, 0])) == 0  # multiple zeros
assert solution.getDecimalValue(build_list([1] * 30)) == (1 << 30) - 1  # maximum length

Test	Why
`[1,0,1]`	Verifies the standard example
`[0]`	Tests smallest possible zero input
`[1]`	Tests smallest possible non-zero input
`[1,1,1]`	Ensures repeated ones are handled correctly
`[0,0,1]`	Verifies leading zeros do not break logic
`[1,0,0,0]`	Tests binary powers of two
`[1,1,0,1]`	Tests general mixed binary digits
`[0,0,0]`	Ensures multiple zeros remain zero
`[1] * 30`	Validates behavior at maximum constraint size

Edge Cases

One important edge case is a linked list containing only a single node. Inputs like [0] or [1] can expose bugs where implementations incorrectly assume multiple nodes exist. The provided solution handles this naturally because the traversal loop works correctly even for a single iteration.

Another important case is leading zeros, such as [0,0,1]. Some incorrect implementations may accidentally ignore early bits or mishandle positional values. The shifting approach correctly preserves binary structure because every processed bit contributes to the final value according to its position.

A third important edge case is the maximum input size of 30 nodes. Although the constraints are small, this still tests whether the implementation efficiently processes the list in linear time without unnecessary memory usage. Since the algorithm uses only one traversal and constant extra space, it scales cleanly to the maximum allowed input size.

A final edge case is when all bits are zero, such as [0,0,0]. Some implementations might incorrectly produce non-zero values if they initialize or update the accumulator incorrectly. Here, repeated left shifts and OR operations with zero correctly preserve the value 0 throughout the traversal.