Convert Binary Number in a Linked List to Integer

Difficulty: Easy | Acceptance: 82.30% | Paid: No Topics: Linked List, Math

Given head which is a reference node to a singly-linked list. The values of each node in the linked-list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit (MSB) is at the head of the linked list.

• Examples
• Constraints
• Bit Manipulation Approach
• String Conversion Approach
• Recursive Approach
• Array Approach

Examples

Example 1:

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 equals (5) in base 10.

Example 2:

Input: head = [0]
Output: 0

Constraints

The number of nodes in the linked list is in the range [1, 30].
Node.val is either 0 or 1.

Bit Manipulation Approach

Intuition Traverse the linked list while building the integer by left-shifting the current result and adding the current node’s value.

Steps

• Initialize result to 0
• Traverse the linked list
• For each node, left-shift result by 1 (multiply by 2) and add the node’s value
• Return the final result

# 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: ListNode) -> int:
        result = 0
        current = head
        while current:
            result = (result << 1) | current.val
            current = current.next
        return result

Complexity

• Time: O(n) where n is the number of nodes in the linked list
• Space: O(1) constant extra space
• Notes: Most efficient approach with optimal time and space complexity

String Conversion Approach

Intuition Convert the linked list to a string representation of the binary number, then parse it to an integer.

Steps

• Traverse the linked list and build a string of binary digits
• Parse the binary string to an integer
• Return the result

# 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: ListNode) -> int:
        binary_str = ""
        current = head
        while current:
            binary_str += str(current.val)
            current = current.next
        return int(binary_str, 2)

Complexity

• Time: O(n) where n is the number of nodes in the linked list
• Space: O(n) for storing the binary string
• Notes: Less space efficient than bit manipulation but more intuitive

Recursive Approach

Intuition Recursively process the linked list, building the integer from the most significant bit to the least significant bit.

Steps

• Base case: if head is null, return 0
• Recursively process the rest of the list
• Combine the result by left-shifting and adding the current node’s value

# 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: ListNode) -> int:
        def helper(node: ListNode, result: int) -> int:
            if node is None:
                return result
            return helper(node.next, (result << 1) | node.val)
        return helper(head, 0)

Complexity

• Time: O(n) where n is the number of nodes in the linked list
• Space: O(n) for the recursion stack
• Notes: Elegant but uses O(n) stack space due to recursion

Array Approach

Intuition Store all values in an array, then compute the integer by iterating from the most significant bit.

Steps

• Traverse the linked list and store all values in an array
• Iterate through the array, computing the decimal value using powers of 2
• Return the result

# 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: ListNode) -> int:
        values = []
        current = head
        while current:
            values.append(current.val)
            current = current.next
        
        result = 0
        n = len(values)
        for i in range(n):
            result += values[i] * (1 << (n - 1 - i))
        return result

Complexity

• Time: O(n) where n is the number of nodes in the linked list
• Space: O(n) for storing the array
• Notes: Less efficient than bit manipulation but demonstrates the mathematical concept clearly