We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert Binary Number in a Linked List to Integer

Number: 1411

Difficulty: Easy

Paid? No

Companies: Bloomberg, Amazon, Salesforce, Oracle, Roblox

Problem Description

Given a singly-linked list where each node's value is either 0 or 1, the linked list represents the binary number with the most significant bit at the head. The task is to convert this binary number to its corresponding decimal (base 10) integer.

Key Insights

  • The linked list contains digits of a binary number, with the head being the most significant bit.
  • As you traverse the list, you can simulate binary-to-decimal conversion by shifting the current result left (multiplying by 2) and adding the current node's value.
  • The linked list length is small (at most 30 nodes), which simplifies concerns about performance or overflow.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), using only constant space for computations.

Solution

We iterate through the linked list and maintain an accumulator to build the decimal value. At each node, we multiply the accumulator by 2 (simulating a left bit shift) and add the node's binary digit (0 or 1). This approach directly converts the binary representation into its decimal form and completes in a single pass through the list.

Code Solutions

Python:

JavaScript:

C++:

Java:

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

def getDecimalValue(head):
    # Initialize the accumulator to 0
    result = 0
    # Traverse each node in the linked list
    while head:
        # Multiply result by 2 (left shift) and add the current node's value
        result = result * 2 + head.val
        # Move to the next node
        head = head.next
    return result

# Example usage:
# Creating a linked list for [1, 0, 1]
node3 = ListNode(1)
node2 = ListNode(0, node3)
node1 = ListNode(1, node2)
print(getDecimalValue(node1))  # Output: 5
← Back to All Questions