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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert Binary Number in a Linked List to Integer

Difficulty: Easy

Problem Description

Given head which is a reference node to a singly-linked list. The value 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 is at the head of the linked list.

Key Insights

  • The linked list represents a binary number, with the head being the most significant bit.
  • Each node's value contributes to the overall value based on its position in the list.
  • The conversion from binary to decimal can be performed by iterating through the linked list and calculating the decimal value incrementally.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list.
Space Complexity: O(1) as we are using a constant amount of space for variables.

Solution

To solve this problem, we will traverse the linked list and maintain a cumulative result for the decimal value. As we iterate through the nodes, we will shift the current result to the left (multiply by 2) and add the current node's value. This approach effectively builds the decimal value from the binary representation.

We will use a simple loop to traverse the linked list until we reach the end, updating our result at each step.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getDecimalValue(head: ListNode) -> int:
    result = 0
    current = head
    while current:
        result = (result << 1) | current.val  # Shift left and add current node's value
        current = current.next
    return result
← Back to All Questions