Problem Description

You are given a reference to the head of a singly-linked list where each node contains either 0 or 1. The linked list represents a binary number, with the most significant bit (leftmost bit) at the head of the list.

Your task is to convert this binary representation into its decimal equivalent and return the decimal value.

For example, if the linked list is 1 -> 0 -> 1, this represents the binary number 101, which equals 5 in decimal.

The solution works by traversing the linked list from head to tail. It maintains a running result ans that starts at 0. For each node visited:

1. The current ans value is left-shifted by 1 bit (equivalent to multiplying by 2)
2. The current node's value (0 or 1) is added using bitwise OR operation

This process effectively builds the decimal number bit by bit. The expression ans = ans << 1 | head.val performs both operations in one step:

• ans << 1 shifts all bits in ans one position to the left
• | head.val adds the current bit to the rightmost position

After processing all nodes, ans contains the final decimal value.

Intuition

When we read a binary number from left to right, we're essentially building up the decimal value by processing each bit in sequence. Consider how we manually convert binary to decimal: for binary 101, we calculate 1×2² + 0×2¹ + 1×2⁰ = 4 + 0 + 1 = 5.

However, there's a more elegant pattern we can observe. As we read each new bit from left to right, we're essentially:

• Taking everything we've seen so far and doubling it (shifting it left)
• Adding the new bit to the rightmost position

For example, processing 101 step by step:

• Start with 0
• Read 1: 0 × 2 + 1 = 1
• Read 0: 1 × 2 + 0 = 2
• Read 1: 2 × 2 + 1 = 5

This naturally leads us to the bit manipulation approach. Multiplying by 2 is equivalent to left-shifting by 1 bit (<< 1), and adding the current bit can be done with bitwise OR (|) since we're only adding to the rightmost position which is guaranteed to be 0 after the shift.

The beauty of this approach is that we don't need to know the length of the linked list beforehand or store all values first. We can compute the decimal value in a single pass, processing each bit as we encounter it, making the solution both time and space efficient.

Learn more about Linked List and Math patterns.

Solution Approach

The solution uses a single traversal approach with bit manipulation to convert the binary linked list to its decimal value.

Algorithm Steps:

1. Initialize a variable ans to 0 to store the decimal result.

2. Traverse the linked list from head to tail using a while loop:

   • While the current node (head) is not None:
     • Update ans using the formula: ans = ans << 1 | head.val
       • ans << 1 left-shifts the current value by one bit position (equivalent to multiplying by 2)
       • | head.val performs a bitwise OR operation to add the current node's value (0 or 1) to the rightmost bit
     • Move to the next node: head = head.next

3. Return the final value of ans

Bit Manipulation Breakdown:

The expression ans << 1 | head.val works as follows:

• Left shift (<<): Moves all bits one position to the left, effectively multiplying by 2
• Bitwise OR (|): Since the rightmost bit after shifting is always 0, OR-ing with head.val (which is either 0 or 1) simply places that value in the rightmost position

Example Walkthrough:

For linked list 1 -> 0 -> 1:

• Initially: ans = 0 (binary: 000)
• Process node 1: ans = 0 << 1 | 1 = 0 | 1 = 1 (binary: 001)
• Process node 0: ans = 1 << 1 | 0 = 2 | 0 = 2 (binary: 010)
• Process node 1: ans = 2 << 1 | 1 = 4 | 1 = 5 (binary: 101)
• Return: 5

This approach processes the linked list in a single pass with O(n) time complexity where n is the number of nodes, and uses O(1) extra space.

Example Walkthrough

Let's walk through converting the linked list 1 -> 1 -> 0 -> 1 to its decimal value.

This represents the binary number 1101, which should equal 13 in decimal.

Step-by-step execution:

Initial State:

• ans = 0 (binary: 0000)
• head points to first node with value 1

Iteration 1: Process node with value 1

• Calculate: ans = ans << 1 | head.val
• ans << 1 = 0 << 1 = 0 (binary: 0000)
• 0 | 1 = 1 (binary: 0001)
• New ans = 1
• Move to next node (value 1)

Iteration 2: Process node with value 1

• Calculate: ans = ans << 1 | head.val
• ans << 1 = 1 << 1 = 2 (binary: 0010)
• 2 | 1 = 3 (binary: 0011)
• New ans = 3
• Move to next node (value 0)

Iteration 3: Process node with value 0

• Calculate: ans = ans << 1 | head.val
• ans << 1 = 3 << 1 = 6 (binary: 0110)
• 6 | 0 = 6 (binary: 0110)
• New ans = 6
• Move to next node (value 1)

Iteration 4: Process node with value 1

• Calculate: ans = ans << 1 | head.val
• ans << 1 = 6 << 1 = 12 (binary: 1100)
• 12 | 1 = 13 (binary: 1101)
• New ans = 13
• Move to next node (reaches None)

Result: Return 13

The algorithm efficiently builds the decimal value bit by bit, treating each new node's value as the next least significant bit to add to our growing result.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. This is because the algorithm traverses the entire linked list exactly once, visiting each node from head to tail. In each iteration, it performs constant time operations: bit shifting (ans << 1), bitwise OR (| head.val), and pointer advancement (head = head.next).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains just two variables: ans to store the accumulated decimal value and the head pointer to traverse the list. No additional data structures or recursive calls are used that would scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles arbitrarily large integers automatically, in languages like Java or C++, you might encounter integer overflow for very long linked lists (typically more than 31-32 nodes).

Problem Example:

# In languages with fixed integer sizes, this could overflow:
# Linked list with 35 nodes: 1->1->1->1->1... (35 ones)
# Result would exceed 32-bit integer maximum (2^31 - 1)

Solution:

• In Python: No action needed as integers can grow arbitrarily large
• In other languages: Use long/long long data types or check for overflow conditions
• Add validation for maximum linked list length if needed

2. Misunderstanding Bit Manipulation Operations

Developers might incorrectly use addition instead of bitwise OR, thinking they're equivalent.

Incorrect Approach:

# Wrong - This works but is conceptually different
decimal_value = (decimal_value << 1) + head.val

# Correct - Using bitwise OR
decimal_value = (decimal_value << 1) | head.val

Why it matters: While both produce the same result when head.val is 0 or 1, the bitwise OR approach:

• Is more semantically correct for bit manipulation
• Would handle edge cases better if node values weren't strictly 0 or 1
• Is typically faster at the CPU level

3. Modifying the Original Linked List

Using head directly for traversal loses the reference to the original list head.

Problem Code:

def getDecimalValue(self, head: ListNode) -> int:
    decimal_value = 0
    original_head = head  # Unnecessary but shows intent to preserve
    while head:
        decimal_value = (decimal_value << 1) | head.val
        head = head.next
    # head is now None, original list reference lost
    return decimal_value

Better Practice:

def getDecimalValue(self, head: ListNode) -> int:
    decimal_value = 0
    current = head  # Use a separate pointer for traversal
    while current:
        decimal_value = (decimal_value << 1) | current.val
        current = current.next
    # head still points to the original list
    return decimal_value

4. Not Handling Edge Cases

Forgetting to consider empty lists or single-node lists.

Potential Issue:

# Without proper null checking
def getDecimalValue(self, head: ListNode) -> int:
    if not head:  # Important edge case check
        return 0
    decimal_value = 0
    while head:
        decimal_value = (decimal_value << 1) | head.val
        head = head.next
    return decimal_value

Note: The original solution handles this correctly since the while loop naturally handles None, but explicit checking makes intent clearer.

5. Alternative Mathematical Approach Confusion

Some might try to calculate using powers of 2 with the wrong direction.

Incorrect Approach:

# Wrong - This assumes we know the length beforehand
def getDecimalValue(self, head: ListNode) -> int:
    result = 0
    power = 0
    while head:
        result += head.val * (2 ** power)  # Wrong direction!
        power += 1
        head = head.next
    return result

Why the bit-shift approach is better:

• Doesn't require knowing the list length in advance
• Processes bits in the correct order (MSB to LSB)
• More efficient than calculating powers of 2