Convert Binary Number in Linked List to Integer

🎯

Convert Binary Number in Linked List to Integer

easyLINKED_LISTAmazonGoogle

Imagine you receive a linked list representing a binary number from a hardware sensor, and you need to convert it into a decimal integer to process it further.

💡 This problem involves traversing a linked list and interpreting its nodes as bits of a binary number. Beginners often struggle because they try to convert the linked list to a string first or do multiple passes, instead of accumulating the integer value on the fly.

📋

Problem Statement

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 number of nodes in the linked list is in the range [1, 10^5].Each node's value is either 0 or 1.

💡

Example

Input"head = [1,0,1]"

Output5

The binary number is 101 which equals 5 in decimal.

• Single node with value 0 → output 0
• Single node with value 1 → output 1
• All nodes are 0 → output 0
• All nodes are 1 → output 2^n - 1 (max value for n bits)

⚠️

Common Mistakes

Trying to convert linked list to integer by first converting to decimal digit string

Incorrect output because digits are binary bits, not decimal digits

✅ Convert bits as binary, not decimal digits; use bit shifts or parse as base 2

Using recursion without considering stack overflow

Runtime error on large inputs due to deep recursion

✅ Use iterative approach for large inputs

Appending bits to string inefficiently (e.g., string concatenation in a loop in Java)

Slower performance due to repeated string copying

✅ Use StringBuilder in Java or equivalent efficient string builder

Not handling single node linked list correctly

Incorrect output or errors if code assumes multiple nodes

✅ Ensure code works for single node linked list

🧠

Brute Force (Convert to String then Parse)

💡 This approach exists because it is the most straightforward way to understand the problem: convert the linked list to a binary string, then parse it as an integer. It helps beginners grasp the problem before optimizing.

Intuition

Traverse the linked list, build a string of bits, then convert that string to an integer using built-in parsing.

Algorithm

1. Initialize an empty string to store bits.
2. Traverse the linked list from head to end, appending each node's value to the string.
3. Use built-in function to convert the binary string to an integer.
4. Return the integer.

💡 The main difficulty is realizing that building a string is simple but inefficient for large inputs, and that parsing the string is a separate step.

</>

Code

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

def getDecimalValue(head: ListNode) -> int:
    bits = ''
    current = head
    while current:
        bits += str(current.val)
        current = current.next
    return int(bits, 2)

# Example usage:
if __name__ == '__main__':
    # Create linked list 1->0->1
    node3 = ListNode(1)
    node2 = ListNode(0, node3)
    node1 = ListNode(1, node2)
    print(getDecimalValue(node1))  # Output: 5

Line Notes

bits = ''Initialize an empty string to accumulate bits from the linked list

while current:Traverse the linked list until the end

bits += str(current.val)Append the current node's bit as a string to the bits accumulator

return int(bits, 2)Convert the binary string to an integer using base 2

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static int getDecimalValue(ListNode head) {
        StringBuilder bits = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            bits.append(current.val);
            current = current.next;
        }
        return Integer.parseInt(bits.toString(), 2);
    }

    public static void main(String[] args) {
        ListNode node3 = new ListNode(1);
        ListNode node2 = new ListNode(0);
        node2.next = node3;
        ListNode node1 = new ListNode(1);
        node1.next = node2;
        System.out.println(getDecimalValue(node1)); // Output: 5
    }
}

Line Notes

StringBuilder bits = new StringBuilder();Use StringBuilder for efficient string concatenation

while (current != null)Traverse the linked list until the end

bits.append(current.val);Append the current node's bit to the string builder

return Integer.parseInt(bits.toString(), 2);Parse the binary string as an integer with base 2

#include <iostream>
#include <string>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getDecimalValue(ListNode* head) {
    std::string bits;
    ListNode* current = head;
    while (current != nullptr) {
        bits += std::to_string(current->val);
        current = current->next;
    }
    return std::stoi(bits, nullptr, 2);
}

int main() {
    ListNode* node3 = new ListNode(1);
    ListNode* node2 = new ListNode(0);
    node2->next = node3;
    ListNode* node1 = new ListNode(1);
    node1->next = node2;
    std::cout << getDecimalValue(node1) << std::endl; // Output: 5
    return 0;
}

Line Notes

std::string bits;Initialize a string to accumulate bits from the linked list

while (current != nullptr)Traverse the linked list until the end

bits += std::to_string(current->val);Append the current node's bit as a string to bits

return std::stoi(bits, nullptr, 2);Convert the binary string to an integer with base 2

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function getDecimalValue(head) {
    let bits = '';
    let current = head;
    while (current !== null) {
        bits += current.val.toString();
        current = current.next;
    }
    return parseInt(bits, 2);
}

// Example usage:
const node3 = new ListNode(1);
const node2 = new ListNode(0, node3);
const node1 = new ListNode(1, node2);
console.log(getDecimalValue(node1)); // Output: 5

Line Notes

let bits = '';Initialize an empty string to collect bits

while (current !== null)Traverse the linked list until the end

bits += current.val.toString();Append the current node's bit as a string to bits

return parseInt(bits, 2);Parse the binary string as an integer with base 2

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the linked list once (O(n)) and build a string of length n, then parse it which is O(n).

💡 For n=20, this means about 20 steps to build the string and 20 steps to parse it, totaling roughly 40 operations.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory and is slower than necessary; good for initial understanding.

🧠

Iterative Running Value with Bit Shifts

💡 This approach improves on the brute force by calculating the integer value on the fly without extra memory, which is more efficient and closer to how computers process binary numbers.

Intuition

As you traverse the linked list, shift the current result left by 1 bit and add the current node's value. This simulates building the binary number from left to right.

Algorithm

1. Initialize an integer result to 0.
2. Traverse the linked list from head to end.
3. For each node, left shift result by 1 (multiply by 2) and add the node's value.
4. Return the final result.

💡 The key insight is that left shifting accumulates the binary number correctly without needing a string.

</>

Code

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
        current = current.next
    return result

# Example usage:
if __name__ == '__main__':
    node3 = ListNode(1)
    node2 = ListNode(0, node3)
    node1 = ListNode(1, node2)
    print(getDecimalValue(node1))  # Output: 5

Line Notes

result = 0Initialize the integer accumulator to zero

while current:Traverse the linked list until the end

result = (result << 1) | current.valShift result left by 1 bit and add current bit using bitwise OR

return resultReturn the accumulated integer value

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static int getDecimalValue(ListNode head) {
        int result = 0;
        ListNode current = head;
        while (current != null) {
            result = (result << 1) | current.val;
            current = current.next;
        }
        return result;
    }

    public static void main(String[] args) {
        ListNode node3 = new ListNode(1);
        ListNode node2 = new ListNode(0);
        node2.next = node3;
        ListNode node1 = new ListNode(1);
        node1.next = node2;
        System.out.println(getDecimalValue(node1)); // Output: 5
    }
}

Line Notes

int result = 0;Initialize the integer accumulator to zero

while (current != null)Traverse the linked list until the end

result = (result << 1) | current.val;Shift result left by 1 bit and add current bit using bitwise OR

return result;Return the accumulated integer value

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getDecimalValue(ListNode* head) {
    int result = 0;
    ListNode* current = head;
    while (current != nullptr) {
        result = (result << 1) | current->val;
        current = current->next;
    }
    return result;
}

int main() {
    ListNode* node3 = new ListNode(1);
    ListNode* node2 = new ListNode(0);
    node2->next = node3;
    ListNode* node1 = new ListNode(1);
    node1->next = node2;
    std::cout << getDecimalValue(node1) << std::endl; // Output: 5
    return 0;
}

Line Notes

int result = 0;Initialize the integer accumulator to zero

while (current != nullptr)Traverse the linked list until the end

result = (result << 1) | current->val;Shift result left by 1 bit and add current bit using bitwise OR

return result;Return the accumulated integer value

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function getDecimalValue(head) {
    let result = 0;
    let current = head;
    while (current !== null) {
        result = (result << 1) | current.val;
        current = current.next;
    }
    return result;
}

// Example usage:
const node3 = new ListNode(1);
const node2 = new ListNode(0, node3);
const node1 = new ListNode(1, node2);
console.log(getDecimalValue(node1)); // Output: 5

Line Notes

let result = 0;Initialize the integer accumulator to zero

while (current !== null)Traverse the linked list until the end

result = (result << 1) | current.val;Shift result left by 1 bit and add current bit using bitwise OR

return result;Return the accumulated integer value

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the linked list once (O(n)) and use only a constant amount of extra space for the integer accumulator.

💡 For n=20, this means about 20 operations and no extra memory beyond a few variables.

Interview Verdict: Accepted and optimal

This is the best approach for this problem, combining clarity and efficiency.

🧠

Recursive Approach with Accumulated Value

💡 This approach uses recursion to accumulate the integer value as we traverse the linked list, helping understand recursion and how to carry state through calls.

Intuition

Recursively process the current node by shifting the accumulated value so far left by 1 and adding the current node's value, then recurse to the next node.

Algorithm

1. Define a helper recursive function that takes the current node and the accumulated integer value so far.
2. If the node is null, return the accumulated value.
3. Update the accumulated value by shifting it left by 1 and adding the current node's value.
4. Recursively call the helper function on the next node with the updated accumulated value.
5. Return the final accumulated value.

💡 The challenge is understanding how to carry the accumulated value through recursive calls instead of building from the end.

</>

Code

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

def getDecimalValue(head: ListNode) -> int:
    def helper(node, acc):
        if node is None:
            return acc
        acc = (acc << 1) | node.val
        return helper(node.next, acc)
    return helper(head, 0)

# Example usage:
if __name__ == '__main__':
    node3 = ListNode(1)
    node2 = ListNode(0, node3)
    node1 = ListNode(1, node2)
    print(getDecimalValue(node1))  # Output: 5

Line Notes

def helper(node, acc):Define a recursive helper function with current node and accumulated value

if node is None:Base case: if node is null, return the accumulated value

acc = (acc << 1) | node.valShift accumulated value left and add current node's bit

return helper(node.next, acc)Recurse to next node with updated accumulated value

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static int getDecimalValue(ListNode head) {
        return helper(head, 0);
    }

    private static int helper(ListNode node, int acc) {
        if (node == null) return acc;
        acc = (acc << 1) | node.val;
        return helper(node.next, acc);
    }

    public static void main(String[] args) {
        ListNode node3 = new ListNode(1);
        ListNode node2 = new ListNode(0);
        node2.next = node3;
        ListNode node1 = new ListNode(1);
        node1.next = node2;
        System.out.println(getDecimalValue(node1)); // Output: 5
    }
}

Line Notes

return helper(head, 0);Start recursion with head node and initial accumulated value 0

if (node == null) return acc;Base case: if node is null, return accumulated value

acc = (acc << 1) | node.val;Shift accumulated value left and add current node's bit

return helper(node.next, acc);Recurse to next node with updated accumulated value

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int helper(ListNode* node, int acc) {
    if (node == nullptr) return acc;
    acc = (acc << 1) | node->val;
    return helper(node->next, acc);
}

int getDecimalValue(ListNode* head) {
    return helper(head, 0);
}

int main() {
    ListNode* node3 = new ListNode(1);
    ListNode* node2 = new ListNode(0);
    node2->next = node3;
    ListNode* node1 = new ListNode(1);
    node1->next = node2;
    std::cout << getDecimalValue(node1) << std::endl; // Output: 5
    return 0;
}

Line Notes

int helper(ListNode* node, int acc) {Recursive helper function with current node and accumulated value

if (node == nullptr) return acc;Base case: if node is null, return accumulated value

acc = (acc << 1) | node->val;Shift accumulated value left and add current node's bit

return helper(node->next, acc);Recurse to next node with updated accumulated value

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function getDecimalValue(head) {
    function helper(node, acc) {
        if (node === null) return acc;
        acc = (acc << 1) | node.val;
        return helper(node.next, acc);
    }
    return helper(head, 0);
}

// Example usage:
const node3 = new ListNode(1);
const node2 = new ListNode(0, node3);
const node1 = new ListNode(1, node2);
console.log(getDecimalValue(node1)); // Output: 5

Line Notes

function helper(node, acc) {Recursive helper function with current node and accumulated value

if (node === null) return acc;Base case: if node is null, return accumulated value

acc = (acc << 1) | node.val;Shift accumulated value left and add current node's bit

return helper(node.next, acc);Recurse to next node with updated accumulated value

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the linked list once, but recursion uses call stack proportional to n.

💡 For n=20, this means 20 recursive calls which might risk stack overflow in some environments.

Interview Verdict: Accepted but risks stack overflow

Good for demonstrating recursion but not recommended for very large inputs due to stack depth.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the iterative bit shift approach in 95% of interviews because it is optimal and easy to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (String Conversion)	O(n)	O(n)	No	N/A	Mention only - never code
2. Iterative Running Value with Bit Shifts	O(n)	O(1)	No	N/A	Code this approach
3. Recursive with Accumulated Value	O(n)	O(n) due to recursion stack	Yes	N/A	Mention as alternative, avoid coding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with clarifying the problem, then explain the brute force approach, and finally present the optimal solution with bit shifts.

How to Present

Step 1: Clarify the input format and constraints.Step 2: Describe the brute force approach of converting to a string and parsing.Step 3: Explain the optimal approach using bit shifts and running value.Step 4: Optionally mention the recursive approach and its tradeoffs.Step 5: Code the optimal iterative solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of linked list traversal, binary number representation, and efficient bit manipulation.

Common Follow-ups

• What if the linked list is extremely long? → Use iterative approach to avoid stack overflow.
• Can you do it in one pass without extra space? → Yes, using bit shifts and running value.

💡 These follow-ups check if you can optimize space and handle large inputs safely.

🔍

Pattern Recognition

When to Use

1) Input is a linked list representing bits; 2) Need to convert binary to decimal; 3) Single pass traversal possible; 4) Bit manipulation is applicable.

Signature Phrases

binary number in linked listconvert to decimal integer

NOT This Pattern When

Problems that require reversing the list or sorting the list are different patterns.

Similar Problems

Sum of Two Linked Lists - similar traversal and accumulationAdd Binary Numbers in Linked List - similar bitwise additionReverse Linked List - linked list manipulation fundamentals

Practice

1. You need to implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?

easy

A. Use a dynamic array and resize it when needed to support all operations.

B. Use a balanced binary search tree keyed by index to support all operations in O(log n).

C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.

D. Use a hash map to store index-to-node mappings for constant time access.

Solution

Solution:

1. Step 1: Understand operation requirements

   The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.

2. Step 2: Evaluate approaches

   Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.

3. Step 3: Choose best approach

   Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Balanced BST supports all required operations efficiently [OK]

Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]

Common Mistakes:

• Assuming linked list provides efficient arbitrary index access
• Thinking arrays support O(1) insertions at head
• Assuming hash maps maintain order

2. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?

easy

A. 1

B. 4

C. 2

D. 3

Solution

1. Step 1: Initial state

   curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.

2. Step 2: First iteration with child

   curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first iteration, curr moves to child node 4 [OK]

Hint: After splicing child, curr moves to child's head node [OK]

Common Mistakes:

• Assuming curr stays at original node after splicing
• Forgetting to move curr to next after flattening
• Confusing tail with child head

3. Given the following code snippet for reversing nodes in k-groups, and the input list 1->2->3->4 with k=2, what is the value of group_prev.next.val after the first group reversal?

easy

A. 4

B. 1

C. 3

D. 2

Solution

Solution:

1. Step 1: Trace first group reversal

   Input list: 1->2->3->4, k=2. First group is nodes 1 and 2. After reversal, group becomes 2->1.

2. Step 2: Identify group_prev.next after reversal

   Initially, group_prev is dummy pointing to 1. After reversal, group_prev.next points to 2, the new head of reversed group.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First group's head after reversal is node with value 2 [OK]

Hint: First group's head after reversal is the kth node [OK]

Common Mistakes:

• Confusing original head with new head after reversal
• Off-by-one in counting nodes
• Misunderstanding pointer updates

4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?

medium

A. O(n) -- recursion stack uses space proportional to list length

B. O(1) -- only constant extra pointers used

C. O(log n) -- recursion depth is halved each call

D. O(n^2) -- due to repeated pointer updates in recursion

Solution

Solution:

1. Step 1: Identify recursion depth

   The helper function recurses once per node, so recursion depth is n.

2. Step 2: Calculate space usage

   Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack proportional to list length [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming constant space due to in-place changes
• Confusing recursion depth with log n
• Overestimating to quadratic space

5. Suppose the partition problem is modified so that nodes can be reused multiple times (e.g., the list represents a multiset with unlimited copies). Which modification to the optimal in-place partition algorithm correctly handles this scenario without breaking the algorithm?

hard

A. Convert the list to arrays, partition values, then rebuild the list to handle duplicates safely.

B. Use the same in-place pointer rearrangement but skip nodes already processed to avoid infinite loops.

C. Modify the algorithm to clone nodes when moving them to the less-than-x partition to preserve original nodes.

D. Use two separate lists with dummy heads and append clones of nodes to handle reuse.

Solution

1. Step 1: Understand the reuse constraint

   Nodes can be reused multiple times, so in-place rearrangement that moves nodes breaks because nodes are unique objects.

2. Step 2: Evaluate modifications

   In-place rearrangement cannot handle duplicates without cloning. Cloning in-place is complex and error-prone. Using arrays to store values and rebuild the list handles duplicates safely and cleanly.

3. Step 3: Compare cloning approaches

   Cloning nodes in-place or in two lists adds complexity and risks pointer errors. Arrays simplify the problem.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Rebuilding from arrays safely handles duplicates and reuse [OK]

Hint: Rebuild list from arrays to handle node reuse safely [OK]

Common Mistakes:

• Trying to rearrange nodes in-place with reuse
• Cloning nodes without updating pointers correctly
• Assuming pointer moves work with reused nodes