Bird
Raised Fist0
Interview Preplinked-list-advancedeasyAmazonGoogle

Convert Binary Number in Linked List to Integer

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (String Conversion)O(n)O(n)NoN/AMention only - never code
2. Iterative Running Value with Bit ShiftsO(n)O(1)NoN/ACode this approach
3. Recursive with Accumulated ValueO(n)O(n) due to recursion stackYesN/AMention 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/5)
1. Consider the following Python code implementing browser history with two stacks. After executing the sequence of operations below, what is the output of the last back call?
browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))
easy
A. "youtube.com"
B. "google.com"
C. "facebook.com"
D. "leetcode.com"

Solution

  1. Step 1: Trace back(1) after visiting youtube.com

    back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".
  2. Step 2: Trace back(1) again and forward(1)

    Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Last forward returns "facebook.com" as expected [OK]
Hint: Back and forward operations move URLs between stacks correctly [OK]
Common Mistakes:
  • Off-by-one errors in popping stacks
  • Confusing forward and back stacks
  • Returning wrong top element after operations
2. Consider the following Python code implementing an optimal linked list. After executing these operations: addAtHead(1), addAtTail(3), addAtIndex(1, 2), what is the value returned by get(1)?
easy
A. 2
B. 1
C. 3
D. -1

Solution

  1. Step 1: Trace addAtHead(1)

    List: dummy -> 1; size=1; tail points to node with val=1.
  2. Step 2: Trace addAtTail(3)

    List: dummy -> 1 -> 3; size=2; tail points to node with val=3.
  3. Step 3: Trace addAtIndex(1, 2)

    Insert 2 at index 1: dummy -> 1 -> 2 -> 3; size=3; tail remains at 3.
  4. Step 4: Trace get(1)

    Index 1 corresponds to node with val=2.
  5. Final Answer:

    Option A -> Option A
  6. Quick Check:

    Inserted 2 at index 1 correctly; get(1) returns 2 [OK]
Hint: Indexing starts after dummy node; careful with traversal loops [OK]
Common Mistakes:
  • Off-by-one in traversal loop
  • Not updating tail on addAtIndex at end
  • Returning wrong node value
3. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?
easy
A. 1 -> 4 -> 2 -> 5
B. 1 -> 2 -> 4 -> 5
C. 2 -> 1 -> 4 -> 5
D. 4 -> 1 -> 2 -> 5

Solution

  1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

    Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.
  2. Step 2: Process nodes

    Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nodes less than 3 appear first in original order, then others [OK]
Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]
Common Mistakes:
  • Swapping values instead of nodes
  • Incorrect pointer updates causing lost nodes
  • Assuming order changes within partitions
4. 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
5. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or nodes appear multiple times). Which modification to the reorder list algorithm is necessary to handle this scenario correctly?
hard
A. Use a hash set to track visited nodes and avoid infinite loops during reordering.
B. No modification needed; the recursive approach handles cycles naturally.
C. Convert the list to an array first to handle duplicates, then reorder using indices.
D. Break the list into halves without reversing the second half to prevent cycles.

Solution

  1. Step 1: Understand node reuse implications

    Reusing nodes or cycles cause infinite loops if not detected during traversal.
  2. Step 2: Modify algorithm to track visited nodes

    Using a hash set to track visited nodes prevents revisiting and infinite loops.
  3. Step 3: Evaluate other options

    Recursive approach alone cannot detect cycles; array conversion adds overhead; skipping reversal breaks reorder logic.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking visited nodes prevents infinite loops in cyclic lists [OK]
Hint: Cycle detection requires visited node tracking [OK]
Common Mistakes:
  • Assuming no cycles exist
  • Relying on recursion without cycle checks
  • Ignoring node reuse effects
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard