# Convert Binary Number in a Linked List to Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer)
Canonical: https://scaleengineer.com/dsa/problems/convert-binary-number-in-a-linked-list-to-integer
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Linked List
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [MathWorks](https://scaleengineer.com/companies/mathworks), [Workday](https://scaleengineer.com/companies/workday)
---
## Problem
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:**

![](https://assets.glich.co/dsa/convert-binary-number-in-a-linked-list-to-integer/image0.png) 

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

**Example 2:**

**Input:** head = [0]
**Output:** 0

**Constraints:**

* The Linked List is not empty.
* Number of nodes will not exceed `30`.
* Each node's value is either `0` or `1`.

# Approaches
## String Conversion (Two Passes)
This approach involves two main steps. First, we traverse the linked list to build a string representation of the binary number. Second, we use a built-in function to parse this binary string into its decimal integer equivalent.
**Time:** O(N), where N is the number of nodes in the linked list. The traversal takes O(N) time, and parsing the string of length N also takes O(N) time. · **Space:** O(N), for the `StringBuilder` which stores the N digits of the binary number.
**Pros:** Simple to understand and implement, especially if you are familiar with string manipulation and built-in parsing functions.
**Cons:** Less efficient in terms of space, as it requires extra O(N) space to store the binary string.; The process of building a string and then parsing it can be slower than direct mathematical calculation due to overhead.
### Explanation
We initialize a `StringBuilder` to accumulate the digits. We iterate through the linked list from the head node to the end. In each step, we append the node's value (either '0' or '1') to the `StringBuilder`. After the traversal is complete, we will have a string like "101". Finally, we use Java's `Integer.parseInt(binaryString, 2)` method to convert this binary string into an integer. This method handles the conversion from base 2 to base 10 for us.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        StringBuilder sb = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            sb.append(current.val);
            current = current.next;
        }
        return Integer.parseInt(sb.toString(), 2);
    }
}
```
### Algorithm
- Initialize a `StringBuilder` named `sb`.
- Create a pointer `current` and set it to `head`.
- Loop while `current` is not `null`:
  - Append `current.val` to `sb`.
  - Move `current` to `current.next`.
- Convert the `StringBuilder` to a string.
- Use `Integer.parseInt(string, 2)` to get the decimal value and return it.

## Manual Calculation (Two Passes)
This approach avoids using extra space for a string by first determining the length of the linked list and then performing the mathematical conversion in a second pass. It calculates the contribution of each bit based on its position.
**Time:** O(N), where N is the number of nodes. We traverse the list twice, so the complexity is O(N) + O(N) = O(N). · **Space:** O(1), as we only use a few variables to store the length, the current sum, and the power, regardless of the list size.
**Pros:** Space efficient, using only O(1) extra space.; The logic directly follows the mathematical definition of binary-to-decimal conversion.
**Cons:** Requires two full traversals of the linked list, which is less efficient than a single-pass solution.
### Explanation
The first pass is dedicated to finding the length of the linked list, let's say `L`. The most significant bit (at the head) corresponds to the power `L-1`. In the second pass, we traverse the list again from the head. We initialize a variable `decimalValue` to 0 and a power counter to `L-1`. For each node, we calculate its decimal contribution as `node.val * 2^power` and add it to `decimalValue`. We then decrement the power for the next node. After iterating through all nodes, `decimalValue` will hold the final result.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        int decimalValue = 0;
        int power = length - 1;
        current = head;
        while (current != null) {
            if (current.val == 1) {
                decimalValue += Math.pow(2, power);
            }
            power--;
            current = current.next;
        }
        return decimalValue;
    }
}
```
### Algorithm
- Initialize `length = 0`.
- Traverse the list once with a pointer `current` starting from `head` to find its `length`.
- Initialize `decimalValue = 0` and `power = length - 1`.
- Reset the `current` pointer to `head`.
- Loop while `current` is not `null`:
  - Add `current.val * (int)Math.pow(2, power)` to `decimalValue`.
  - Decrement `power`.
  - Move `current` to `current.next`.
- Return `decimalValue`.

## Bit Manipulation (Single Pass)
This is the most optimal approach. It processes the linked list in a single pass, building the decimal number iteratively. Each time we visit a new node, we shift the current result to the left and add the new bit's value.
**Time:** O(N), as it requires only one traversal of the linked list. · **Space:** O(1), as it uses only a single variable to store the accumulating decimal value.
**Pros:** Highly efficient in both time and space.; It solves the problem in a single pass with constant extra space.; The logic is elegant and concise.
**Cons:** The bit manipulation logic might be slightly less intuitive for beginners compared to the string conversion method.
### Explanation
We can think of building the decimal number from left to right (from MSB to LSB). We start with an initial result of 0. As we traverse the list, for each node, we perform two operations:
1.  **Shift:** We multiply our current result by 2. This is equivalent to a left bit shift (`<< 1`), which makes space for the next bit. For example, if we have processed `10` (binary, which is 2 in decimal) and the next bit is `1`, shifting `10` left gives `100` (binary, 4 in decimal).
2.  **Add/OR:** We add the value of the current node (`0` or `1`) to the shifted result. This is equivalent to a bitwise OR (`|`) with the node's value. Continuing the example, `100 | 1` gives `101` (binary, 5 in decimal).
We repeat this for every node in the list. The final result after the loop is the decimal equivalent.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int num = 0;
        ListNode current = head;
        while (current != null) {
            // Left shift the current number by 1 and add the new bit.
            num = (num << 1) | current.val;
            // Or using arithmetic: num = num * 2 + current.val;
            current = current.next;
        }
        return num;
    }
}
```
### Algorithm
- Initialize `decimalValue = 0`.
- Create a pointer `current` and set it to `head`.
- Loop while `current` is not `null`:
  - Update `decimalValue`: `decimalValue = (decimalValue << 1) | current.val`.
  - Move `current` to `current.next`.
- Return `decimalValue`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int getDecimalValue ( ListNode head ) { int ans = 0 ; for (; head != null ; head = head . next ) { ans = ans << 1 | head . val ; } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {number} */ var getDecimalValue = function ( head ) { let ans = 0 ; for (; head ; head = head . next ) { ans = ( ans << 1 ) | head . val ; } return ans ; };
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int getDecimalValue ( ListNode * head ) { int ans = 0 ; for (; head ; head = head -> next ) { ans = ans << 1 | head -> val ; } return ans ; } };
```

### Python

```python
# 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 : ans = 0 while head : ans = ans << 1 | head . val head = head . next return ans
```