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. 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. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?

medium

A. O(n), because traversal is needed to find the tail

B. O(log n), because the list is balanced using sentinel nodes

C. O(1), because the tail pointer allows direct access to the last node

D. O(n), because updating the size requires traversal

Solution

1. Step 1: Identify operation steps

   addAtTail uses the tail pointer to append a new node directly without traversal.

2. Step 2: Analyze complexity

   Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Tail pointer eliminates traversal, so addAtTail is constant time [OK]

Hint: Tail pointer enables O(1) tail insertions [OK]

Common Mistakes:

• Assuming traversal needed to find tail
• Confusing size update cost
• Thinking sentinel nodes balance list

3. Examine the following buggy code snippet from an optimal linked list implementation. Which line contains the subtle bug that can cause the tail pointer to point to a deleted node after a deletion at the tail?

medium

A. Line 8: self.tail = prev

B. Line 6: prev.next = prev.next.next

C. Line 3: if index < 0 or index >= self.size:

D. Line 7: if index == self.size - 1:

Solution

1. Step 1: Understand tail update condition

   The tail pointer should update when deleting the last node, which is at index size-1 before deletion.

2. Step 2: Identify bug

   At line 8, the tail pointer is set to prev, but prev may not be the correct new tail if the deleted node was the last node. The tail pointer should be updated after size decrement and possibly set to the correct node.

3. Step 3: Correct fix

   Update tail pointer after size decrement and ensure it points to the last node in the list.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tail pointer update must correctly reflect the new last node after deletion [OK]

Hint: Tail pointer update must be done carefully after deletion [OK]

Common Mistakes:

• Updating tail before size decrement
• Not updating tail on last node deletion
• Incorrect traversal to prev node

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