Bird
Raised Fist0
Interview Preplinked-list-advancedeasyAmazonGoogle

Convert Binary Number in Linked List to Integer

Choose your preparation mode4 modes available
📋
Problem

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.

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.
Edge cases: Single node with value 0 → output 0Single node with value 1 → output 1All nodes are 0 → output 0
</>
IDE
def getDecimalValue(head: ListNode) -> int:public int getDecimalValue(ListNode head)int getDecimalValue(ListNode* head)function getDecimalValue(head)
def getDecimalValue(head):
    # Write your solution here
    pass
class Solution {
    public int getDecimalValue(ListNode head) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int getDecimalValue(ListNode* head) {
    // Write your solution here
    return 0;
}
function getDecimalValue(head) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 0Returning 0 for all inputs due to uninitialized or reset accumulator.✅ Initialize result = 0 before loop and update with result = (result << 1) | node.val inside loop.
Wrong: Wrong decimal due to off-by-one bit shiftShifting bits after adding current node value instead of before.✅ Shift result left first, then OR with current bit: result = (result << 1) | node.val.
Wrong: Wrong decimal due to skipping nodesGreedy approach that skips some bits or processes only some nodes.✅ Process every node in order without skipping to accumulate bits correctly.
Wrong: TLE or timeoutUsing string concatenation or recursion without memoization causing O(n^2) or worse.✅ Use iterative bit shift accumulation in O(n) time.
✓
Test Cases
t1_01basic
Input{"head":[1,0,1]}
Expected5

The binary number is 101 which equals 5 in decimal.

t1_02basic
Input{"head":[1,1,0,1]}
Expected13

Binary 1101 equals decimal 13.

t2_01edge
Input{"head":[0]}
Expected0

Single node with value 0 should return 0.

t2_02edge
Input{"head":[1]}
Expected1

Single node with value 1 should return 1.

t2_03edge
Input{"head":[0,0,0,0]}
Expected0

All nodes zero should return 0 regardless of length.

t3_01corner
Input{"head":[1,0,1,0,1,0,1]}
Expected85

Binary 1010101 equals decimal 85.

t3_02corner
Input{"head":[1,1,1,1,1]}
Expected31

All ones for 5 bits equals 2^5 - 1 = 31.

t3_03corner
Input{"head":[1,0,0,1,1]}
Expected19

Binary 10011 equals decimal 19.

t4_01performance
Input{"head":[1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0]}
⏱ Performance - must finish in 2000ms

Large input with n=100 nodes to test O(n) time complexity within 2 seconds.

Practice

(1/5)
1. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)
easy
A. [1, 2, 3, 4]
B. [1, 3, 2, 4]
C. [2, 4, 1, 3]
D. [1, 3, 4, 2]

Solution

  1. Step 1: Trace first iteration of while loop

    odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.
  2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

    Final list order: 1 -> 3 -> 2 -> 4.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]
Hint: Odd nodes first, then even nodes in original order [OK]
Common Mistakes:
  • Confusing node values with indices
  • Off-by-one errors in pointer updates
2. Consider the following Python code implementing the recursive reorder list approach. Given the input list 1->2->3, what is the printed output after calling reorderList(n1)?
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            back.next = None
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
    print(curr.val, end=' ')
    curr = curr.next
easy
A. 1 3
B. 1 2 3
C. 1 3 2
D. 3 2 1

Solution

  1. Step 1: Trace helper calls with input 1->2->3

    Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.
  2. Step 2: Verify final list traversal output

    Prints nodes in order: 1 3 2, confirming correct reorder.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output matches reorder pattern for 3 nodes [OK]
Hint: Small input trace confirms reorder sequence [OK]
Common Mistakes:
  • Assuming no reorder happens
  • Stopping recursion too early
  • Misplacing next pointers
3. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?
easy
A. [[1, 2], [3, 4], []]
B. [[1, 2], [3], [4]]
C. [[1, 2], [3], [4, None]]
D. [[1], [2], [3, 4]]

Solution

  1. Step 1: Calculate total nodes and part sizes

    Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.
  2. Step 2: Assign nodes to parts

    Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
  • Assigning remainder nodes to last parts
  • Off-by-one in part sizes
  • Returning fewer than k parts
4. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.
class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]
medium
A. Line where back_stack.append(url) is called in visit
B. Line where forward_stack.clear() should be called but is missing in visit
C. Line where back_stack.pop() is called in back method
D. Line where forward_stack.pop() is called in forward method

Solution

  1. Step 1: Identify visit method behavior

    Visit appends new URL but does not clear forward_stack, so forward history remains outdated.
  2. Step 2: Understand impact on forward navigation

    Without clearing forward_stack, forward() returns stale pages that should have been discarded.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Clearing forward_stack on visit is essential to maintain correct forward history [OK]
Hint: Visit must clear forward history to avoid stale pages [OK]
Common Mistakes:
  • Forgetting to clear forward stack on visit
  • Incorrectly popping from back stack
  • Mismanaging stack boundaries
5. Identify the bug in the following code snippet for splitting a linked list into k parts:
medium
A. Line where curr is advanced without checking if curr is None, causing AttributeError.
B. Line where tails[i].next is set to curr without checking if curr is None.
C. Line where tails[i].next is set to None, which breaks the list prematurely.
D. Line where dummy_heads are created, which wastes extra space.

Solution

  1. Step 1: Analyze pointer advancement

    Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.
  2. Step 2: Identify potential error

    If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing None check before curr = curr.next causes runtime error [OK]
Hint: Always check curr is not None before accessing curr.next [OK]
Common Mistakes:
  • Forgetting None check before pointer advance
  • Incorrectly cutting list by setting next to None too early
  • Misusing dummy heads
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