Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The list presents bits from most significant to least significant. Appending a bit to a binary prefix doubles its value and adds the bit, so a running accumulator can evaluate the number in list order.

Approach

Start the accumulator at zero. At each node, shift it left once and combine the node's zero-or-one value with bitwise OR, then advance to the next node. Return the accumulator at the end. The shift creates a zero low bit before the OR, making this equivalent to multiplying by two and adding the new digit. No reversal or list modification is required.

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

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

        while head:
            res = (res << 1) | head.val
            head = head.next

        return res

Complexity analysis

For N linked-list nodes, the traversal takes O(N) time and carries only one accumulator, so auxiliary space is O(1).