Convert Binary Number in a Linked List to Integer
EasyPrompt
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 10Example 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
0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
StringBuildernamedsb. - Create a pointer
currentand set it tohead. - Loop while
currentis notnull:- Append
current.valtosb. - Move
currenttocurrent.next.
- Append
- Convert the
StringBuilderto a string. - Use
Integer.parseInt(string, 2)to get the decimal value and return it.
Walkthrough
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.
/** * 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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
length = 0. - Traverse the list once with a pointer
currentstarting fromheadto find itslength. - Initialize
decimalValue = 0andpower = length - 1. - Reset the
currentpointer tohead. - Loop while
currentis notnull:- Add
current.val * (int)Math.pow(2, power)todecimalValue. - Decrement
power. - Move
currenttocurrent.next.
- Add
- Return
decimalValue.
Walkthrough
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.
/** * 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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
decimalValue = 0. - Create a pointer
currentand set it tohead. - Loop while
currentis notnull:- Update
decimalValue:decimalValue = (decimalValue << 1) | current.val. - Move
currenttocurrent.next.
- Update
- Return
decimalValue.
Walkthrough
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:
- 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 processed10(binary, which is 2 in decimal) and the next bit is1, shifting10left gives100(binary, 4 in decimal). - Add/OR: We add the value of the current node (
0or1) to the shifted result. This is equivalent to a bitwise OR (|) with the node's value. Continuing the example,100 | 1gives101(binary, 5 in decimal). We repeat this for every node in the list. The final result after the loop is the decimal equivalent.
/** * 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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
/** * 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 ; } }/** * 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 ; };/** * 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 ; } };# 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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.