Convert Binary Number in Linked List to Integer

📋

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
}

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

Try testing your code on single-node and all-zero inputs to catch base case bugs.

Consider tricky inputs that expose off-by-one or greedy mistakes.

Prepare for large inputs by ensuring your solution runs in linear time.

t1_01basic

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

Expected5

⏱ Performance - must finish in 2000ms

The binary number is 101 which equals 5 in decimal.

💡 Think about how to convert binary digits to decimal by processing each bit.

💡 Use bit shifting or multiply the accumulated value by 2 before adding the next bit.

💡 Iterate through the list, updating result = (result << 1) | current_node_val.

Why it failed: Incorrect output means the binary to decimal conversion logic is wrong. Fix by accumulating result with bit shifts: result = (result << 1) | node.val.

✓ Correctly converts binary linked list to decimal using bit shifts.

t1_02basic

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

Expected13

⏱ Performance - must finish in 2000ms

Binary 1101 equals decimal 13.

💡 Remember each new bit shifts the current number left by one.

💡 Check that you handle all nodes, not just the first few.

💡 Use result = (result << 1) | node.val for each node.

Why it failed: Output incorrect due to missing or incorrect bit shift logic. Fix by shifting result left and OR with current bit for each node.

✓ Correctly processes all bits to produce decimal value.

t2_01edge

Input{"head":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single node with value 0 should return 0.

💡 Test the smallest input size: one node only.

💡 Ensure your code handles single-node lists correctly.

💡 Return the node's value directly if only one node.

Why it failed: Fails single-node zero case, likely returns non-zero or errors. Fix by handling single node properly without assumptions.

✓ Handles single-node zero input correctly.

t2_02edge

Input{"head":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single node with value 1 should return 1.

💡 Check single-node list with value 1.

💡 Make sure no extra shifts or operations corrupt the value.

💡 Return node.val directly if list length is one.

Why it failed: Fails single-node one case, possibly returns 0 or wrong value. Fix by returning node.val for single node.

✓ Correctly returns 1 for single-node input.

t2_03edge

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

Expected0

⏱ Performance - must finish in 2000ms

All nodes zero should return 0 regardless of length.

💡 Test all zero bits to confirm no accidental addition.

💡 Ensure accumulation does not add any value for zero bits.

💡 Result should remain zero after processing all nodes.

Why it failed: Fails all-zero input, returns non-zero. Fix by correctly accumulating bits without adding for zero values.

✓ Correctly returns 0 for all-zero input.

t3_01corner

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

Expected85

⏱ Performance - must finish in 2000ms

Binary 1010101 equals decimal 85.

💡 Beware of off-by-one errors in bit shifts.

💡 Check that you shift before adding the current bit, not after.

💡 Use result = (result << 1) | node.val, not result = result | (node.val << i).

Why it failed: Fails due to off-by-one bit shift error, producing wrong decimal. Fix by shifting result left before OR with current bit.

✓ Correctly handles bit shifts without off-by-one errors.

t3_02corner

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

Expected31

⏱ Performance - must finish in 2000ms

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

💡 Check if your code mistakenly treats this as unbounded repetition.

💡 Confirm you process each node exactly once (0/1 knapsack analogy).

💡 Ensure no repeated addition or double counting of bits.

Why it failed: Fails by counting bits multiple times or using unbounded logic. Fix by processing each node exactly once in order.

✓ Correctly processes each node once for final decimal.

t3_03corner

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

Expected19

⏱ Performance - must finish in 2000ms

Binary 10011 equals decimal 19.

💡 Beware of greedy approaches that pick only some bits.

💡 Make sure to process all bits in order, not just the largest ones.

💡 Accumulate bits sequentially with shifts, do not skip nodes.

Why it failed: Fails due to greedy skipping bits, resulting in wrong decimal. Fix by processing all nodes in order without skipping.

✓ Correctly accumulates all bits sequentially.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Use an O(n) approach with a single pass through the list.

💡 Avoid string concatenation or recursion that increases complexity.

💡 Use bit shifts to accumulate the result efficiently.

Why it failed: TLE occurs due to O(n^2) or exponential complexity, e.g. string concatenation or recursion without memoization. Fix by using iterative bit shift accumulation.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. 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

2. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Extract all node values into arrays, reorder them, then rebuild the list.

B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.

C. Sort the entire linked list using merge sort and then split at value x.

D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   In-place rearrangement achieves O(n) time and O(1) space [OK]

Hint: In-place pointer rearrangement is O(1) space [OK]

Common Mistakes:

• Assuming sorting is needed to partition
• Using extra arrays or lists increases space
• Believing two separate lists always use constant space

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

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 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)

5. What is the time complexity of the optimal in-place split algorithm for splitting a linked list of length n into k parts, and why?

medium

A. O(n) because splitting is done in a single pass without extra overhead.

B. O(n * k) because for each part, we traverse nodes up to part size.

C. O(n + k) because we first count nodes in one pass, then split in one pass plus overhead for k parts.

D. O(k) because the algorithm mainly depends on the number of parts.

Solution

1. Step 1: Identify passes over the list

   One pass to count total nodes (O(n)), one pass to split nodes into k parts (O(n)).

2. Step 2: Account for overhead

   Creating dummy heads and managing k parts adds O(k) overhead, but does not dominate.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes over n plus O(k) overhead is O(n), since k ≤ n [OK]

Hint: Counting + splitting passes plus k overhead -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*k)
• Ignoring overhead of dummy heads
• Confusing single pass with O(n) ignoring k