Convert Binary Number in a Linked List to Integer solution and explanation
Cisco
Google
9 more videos on this problem
Convert Binary Number in a Linked List to Integer | LeetCode 1290 | C++, Java, PythonKnowledge Center · 7:34 · 14K views
Convert Binary Number in a Linked List to Integer | Live Coding with Explanation | Leetcode #1290Algorithms Made Easy · 2:26 · 5K views
Convert Binary Number in a Linked List to Integer | Leet code 1290 | Theory explained + Python codeSai Anish Malla · 11:28 · 3K views
Convert Binary Number in a Linked List to Integer | Leetcode 1290 | Live coding session 🔥🔥🔥🔥 | O(n)Coding Decoded · 5:14 · 555 views
1290. Convert Binary Number in a Linked List to Integer | Leetcode Daily - PythonLeetcode Daily · 4:37 · 504 views
Daily Leetcode #1931: Jul 14, 2025 - 1290. Convert Binary Number in a Linked List to IntegerProgramming Live with Larry · 4:14 · 468 views
LeetCode 1290. [easy] Convert Binary Number in a Linked List to IntegerFrancesco Manicardi · 3:20 · 245 views
Daily Leetcode #215: Nov 01, 2020 - 1290. Convert Binary Number in a Linked List to IntegerProgramming Live with Larry · 2:50 · 225 views
Convert Binary Number in a Linked List to Integer | LeetCode 1290 | Coders CampCoders Camp · 8:10 · 216 views
Daily Leetcode #616: Dec 07, 2021 - 1290. Convert Binary Number in a Linked List to IntegerProgramming Live with Larry · 3:22 · 165 views
The 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:
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
0or1.
Approach overview
Problem Overview: A singly linked list stores a binary number where each node contains either 0 or 1. The head represents the most significant bit. Traverse the list and convert this binary sequence into its decimal integer value.
Approach 1: Bit Manipulation (O(n) time, O(1) space)
This approach treats the traversal like constructing a binary number bit by bit. Start with result = 0. For every node, shift the current value left by one (result << 1) and add the node’s bit using | node.val or simple addition. Each iteration effectively multiplies the current value by two and appends the new bit. The algorithm performs a single pass through the linked list, making it the most direct and efficient solution. Time complexity is O(n) and space complexity is O(1).
Approach 2: Reverse Iteration and Power of Two (O(n) time, O(n) space)
This method first collects all node values into an array while iterating through the list. After that, iterate the array from right to left and compute the decimal value using powers of two. For each bit at index i, add bit * 2^position to the result. The logic mirrors standard binary-to-decimal conversion using math. While still linear time, this approach uses extra memory to store the bits before computing the final value. Time complexity is O(n) and space complexity is O(n).
Recommended for interviews: The Bit Manipulation approach is the expected solution. It processes the list in one pass with constant space and clearly demonstrates understanding of binary operations. The power-of-two approach works but adds unnecessary memory overhead. Interviewers typically want to see how you apply bit manipulation while traversing a linked list.
Approach 1: Bit Manipulation
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
result = 0
while head:
result = (result << 1) | head.val
head = head.next
return resultclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public int getDecimalValue(ListNode head) {
int result = 0;
while (head != null) {
result = (result << 1) | head.val;
head = head.next;
}
return result;
}
}struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int getDecimalValue(ListNode* head) {
int result = 0;
while (head != NULL) {
result = (result << 1) | head->val;
head = head->next;
}
return result;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var getDecimalValue = function(head) {
let result = 0;
while (head !== null) {
result = (result << 1) | head.val;
head = head.next;
}
return result;
};#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
int getDecimalValue(struct ListNode* head) {
int result = 0;
while (head != NULL) {
result = (result << 1) | head->val;
head = head->next;
}
return result;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public int GetDecimalValue(ListNode head) {
int result = 0;
while (head != null) {
result = (result << 1) | head.val;
head = head.next;
}
return result;
}
}The Python getDecimalValue function iterates through the linked list, constructing the decimal integer by shifting and OR-ing values from each node.
Time Complexity: O(n), with n being the linked list node count.
Space Complexity: O(1), since only a few local variables are used.
Approach 2: Reverse Iteration and Power of Two
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
length = 0
current = head
while current:
length += 1
current = current.next
result = 0
current = head
while current:
result += current.val * (2 ** (length - 1))
length -= 1
current = current.next
return resultclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public int getDecimalValue(ListNode head) {
int len = 0, result = 0;
ListNode current = head;
while (current != null) {
len++;
current = current.next;
}
current = head;
while (current != null) {
result += current.val * Math.pow(2, --len);
current = current.next;
}
return result;
}
}#include <cmath>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int getDecimalValue(ListNode* head) {
int len = 0, result = 0;
ListNode* curr = head;
while (curr) {
len++;
curr = curr->next;
}
curr = head;
while (curr) {
result += curr->val * pow(2, --len);
curr = curr->next;
}
return result;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}
var getDecimalValue = function(head) {
let length = 0;
let current = head;
while (current !== null) {
length++;
current = current.next;
}
let result = 0;
current = head;
while (current !== null) {
result += current.val * Math.pow(2, --length);
current = current.next;
}
return result;
};#include <stdlib.h>
#include <math.h>
struct ListNode {
int val;
struct ListNode *next;
};
int getDecimalValue(struct ListNode* head) {
int count = 0;
struct ListNode* current = head;
while (current != NULL) {
count++;
current = current->next;
}
int result = 0;
current = head;
while (current != NULL) {
result += current->val * pow(2, --count);
current = current->next;
}
return result;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public int GetDecimalValue(ListNode head) {
int len = 0, result = 0;
ListNode current = head;
while (current != null) {
len++;
current = current.next;
}
current = head;
while (current != null) {
result += current.val * (int)Math.Pow(2, --len);
current = current.next;
}
return result;
}
}The Python version operates similarly by first counting nodes to establish ordering with powers of two, and followed by accumulating the decimal value through a second, orderly pass.
Time Complexity: O(n), necessitating two scans.
Space Complexity: O(1), aside from inherent segment storage.
Approach 3: Traverse the Linked List
We use a variable ans to record the current decimal value, with an initial value of 0.
Traverse the linked list. For each node, left-shift ans by one bit, then perform a bitwise OR with the current node's value. After traversal, ans is the decimal value.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function getDecimalValue(head: ListNode | null): number {
let ans = 0;
for (; head; head = head.next) {
ans = (ans << 1) | head.val;
}
return ans;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getDecimalValue(head *ListNode) (ans int) {
for ; head != nil; head = head.Next {
ans = ans<<1 | head.Val
}
return
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn get_decimal_value(mut head: Option<Box<ListNode>>) -> i32 {
let mut ans = 0;
while let Some(node) = head {
ans = (ans << 1) | node.val;
head = node.next;
}
ans
}
}/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return Integer
*/
function getDecimalValue($head) {
$ans = 0;
while ($head !== null) {
$ans = ($ans << 1) | $head->val;
$head = $head->next;
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(n), with n being the linked list node count. |
| Reverse Iteration and Power of Two | Time Complexity: O(n), necessitating two scans. |
| Traverse the Linked List | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation | O(n) | O(1) | Best general solution. Single pass through the linked list with constant memory. |
| Reverse Iteration and Power of Two | O(n) | O(n) | Useful for learning binary-to-decimal conversion or when storing nodes in an array for later processing. |
Frequently asked questions
Is Convert Binary Number in a Linked List to Integer easy or hard?
Convert Binary Number in a Linked List to Integer is classified as an Easy problem with an acceptance rate above 80%. The challenge focuses on recognizing the binary accumulation pattern while traversing a linked list.
Convert Binary Number in a Linked List to Integer Python/Java solution
In Python or Java, iterate through the linked list and update an integer variable using result = (result << 1) + node.val. The same logic works across C++, JavaScript, and C#. This approach maintains O(n) time and O(1) space.
How to solve Convert Binary Number in a Linked List to Integer in O(n)?
Traverse the linked list from head to tail while maintaining an integer accumulator. At each node compute result = (result << 1) + node.val. The left shift multiplies the current number by two and appends the next binary digit, producing the decimal value in a single pass.
What is the best approach for Convert Binary Number in a Linked List to Integer?
The best approach uses bit manipulation while traversing the linked list. Start with result = 0, then for each node shift the current result left by one and add the node value. This builds the binary number incrementally in O(n) time and O(1) space.
Is Convert Binary Number in a Linked List to Integer asked at Google/Amazon/Meta?
Binary conversion and linked list traversal problems appear frequently in technical interviews at companies like Amazon, Google, and Meta. This specific problem is commonly used to test understanding of bit manipulation and basic linked list iteration.
What data structure is used in Convert Binary Number in a Linked List to Integer?
The core data structure is a singly linked list where each node stores a binary digit (0 or 1). The algorithm processes nodes sequentially and may optionally use bit manipulation operations to construct the final integer value.
What is the time complexity of Convert Binary Number in a Linked List to Integer?
The optimal solution runs in O(n) time because each node in the linked list is visited exactly once. Space complexity is O(1) when using the bit manipulation approach since no extra data structures are required.