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 are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child list may also have one or more children of its own, and so on, creating a multilevel data structure. Which approach guarantees an optimal solution to flatten this multilevel doubly linked list into a single-level doubly linked list preserving the original order?

easy

A. Use a recursive depth-first traversal that returns the tail of each flattened child list and connects it back to the parent list.

B. Use a breadth-first traversal with a queue to process nodes level by level, appending child lists at the end of the current level.

C. Iteratively traverse the list, and whenever a node has a child, find the tail of the child list and splice it between the current node and its next node, updating all pointers in-place without extra space.

D. Apply a greedy approach that always flattens the child list with the largest number of nodes first to minimize pointer updates.

Solution

1. Step 1: Understand the problem structure

   The problem requires flattening a multilevel doubly linked list into a single-level list while preserving the order of nodes as they appear in depth-first traversal.

2. Step 2: Evaluate approaches

   Recursive DFS (A) works but uses extra stack space. The in-place iterative approach (B) efficiently flattens by splicing child lists without extra space. BFS (C) changes order and is not optimal. Greedy (D) does not guarantee correct order.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place iterative flattening preserves order and uses O(1) extra space [OK]

Hint: In-place iterative splicing preserves order and uses no extra space [OK]

Common Mistakes:

• Confusing BFS with DFS order
• Assuming recursion is always optimal
• Thinking greedy approach reduces pointer updates

2. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use a recursive approach that reverses k nodes at a time and recurses on the rest, relying on call stack for reversal.

B. Apply a dynamic programming approach to store reversed sublists and combine them for the final result.

C. Iteratively traverse the list, reversing each group of k nodes using a helper function, and reconnect groups with pointer manipulation.

D. Use a greedy approach that reverses nodes whenever possible without checking group boundaries.

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing nodes in groups of k, preserving the order of leftover nodes if fewer than k remain.

2. Step 2: Evaluate approaches

   Recursive approach (A) uses extra stack space and risks overflow; DP (B) is not applicable; greedy (D) fails on partial groups. Iterative with helper (C) reverses groups efficiently with O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative helper method is standard optimal solution [OK]

Hint: Iterative helper reversal is optimal for O(1) space [OK]

Common Mistakes:

• Confusing recursion with iterative approach
• Assuming DP applies to linked list reversal
• Ignoring partial group handling

3. What is the time and space complexity of the optimal in-place partition algorithm for a linked list of length n around value x?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n), Space: O(n)

C. Time: O(n^2), Space: O(1)

D. Time: O(n log n), Space: O(1)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm traverses the list once, performing constant-time pointer operations per node, so time is O(n).

2. Step 2: Check if recursion stack adds extra space

   No recursion or extra data structures are used; only a few pointers are maintained, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant pointers -> O(n) time and O(1) space [OK]

Hint: Single pass with pointer updates -> O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing with sorting complexity O(n log n)
• Assuming extra arrays cause O(n) space
• Mistaking pointer updates as nested loops causing O(n^2)

4. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

5. Suppose the linked list with random pointers can contain cycles formed by next pointers (i.e., the list is not necessarily acyclic). Which modification to the optimal weaving approach is necessary to correctly copy such a list?

hard

A. Use a hash map to track visited nodes to avoid infinite loops during traversal.

B. Modify the separation step to break cycles before copying nodes.

C. No modification needed; the weaving approach works as is for cyclic lists.

D. Use recursion with memoization to handle cycles safely.

Solution

1. Step 1: Understand cycle impact on weaving approach

   The weaving approach assumes linear traversal; cycles cause infinite loops.

2. Step 2: Identify necessary modification

   Tracking visited nodes with a hash map prevents infinite loops by stopping revisits.

3. Step 3: Evaluate other options

   Breaking cycles before copying is complex; recursion risks stack overflow; no modification leads to infinite loop.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map prevents infinite traversal in cyclic lists [OK]

Hint: Cycles require visited tracking to avoid infinite loops [OK]

Common Mistakes:

• Assuming acyclic list always
• Trying to break cycles before copying
• Using recursion without cycle detection