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.
Example 1:
Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10
Example 2:
Input: head = [0] Output: 0
Constraints:
30.0 or 1.This approach involves traversing the linked list and building the decimal value using bit manipulation. As the linked list is traversed, the current result is shifted left by one bit (equivalent to multiplying by 2), and the current node's value is added using the OR operation.
The function getDecimalValue traverses the linked list, updating the result by left-shifting it by one bit and then OR-ing it with the current node's value. This operation effectively constructs the binary number bit by bit.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of additional space.
This approach involves traversing the linked list twice. First, to count the nodes (and hence determine the power of two to start with) and second to compute the decimal value by iterating through the list again, multiplying each binary digit by the appropriate power of two.
In this implementation, we traverse the list to calculate the length, which aids in determining the highest power of two needed. A second pass through the list allows for calculation of the decimal value, multiplying each node value by 2 raised to the correct power.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes, but involves two passes.
Space Complexity: O(1), since it uses constant space plus a few variables.
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(n), where n is the number of nodes in the linked list. |
| Reverse Iteration and Power of Two | Time Complexity: O(n), where n is the number of nodes, but involves two passes. |
Convert Binary Number in a Linked List to Integer | EP 6 • Fraz • 27,244 views views
Watch 9 more video solutions →Practice Convert Binary Number in a Linked List to Integer with our built-in code editor and test cases.
Practice on FleetCode