Convert Binary Number in Linked List to Integer

▶

Steps

setup

Setup: Define linked list nodes

Create the linked list nodes representing the binary number 1 -> 0 -> 1. The head pointer points to the first node with value 1.

💡 Initializing the linked list structure is essential to visualize how the algorithm traverses and processes each node.

Line:

node3 = ListNode(1)
node2 = ListNode(0, node3)
node1 = ListNode(1, node2)
head = node1

💡 The linked list structure is now ready for traversal, with each node holding a binary digit.

setup

Start recursion: Call helper with head node and acc=0

Begin the recursive helper function with the head node (value 1) and an initial accumulated value of 0.

💡 Starting recursion with acc=0 sets the base for accumulating the binary number as we traverse nodes.

Line:

return helper(head, 0)

💡 The recursion will process each node, updating the accumulated value step-by-step.

compare

Check base case: node is not None

Check if the current node is None. Since node 1 exists, proceed to update the accumulated value.

💡 The base case ends recursion; here we confirm we still have nodes to process.

Line:

if node is None:
    return acc

💡 Recursion continues as we have a valid node to process.

fill_cells

Update acc with node 1's value

Shift acc left by 1 (0 << 1 = 0) and OR with node.val (1), updating acc to 1.

💡 Bitwise shift and OR combine to append the current binary digit to acc.

Line:

acc = (acc << 1) | node.val

💡 The accumulated value now represents the binary number formed so far.

traverse

Recursive call on node 2 with acc=1

Call helper recursively on the next node (value 0) with updated acc=1.

💡 Recursion moves forward to process the next binary digit.

Line:

return helper(node.next, acc)

💡 The recursion stack grows as we move deeper into the list.

compare

Check base case: node 2 is not None

Confirm node 2 exists, so continue recursion.

💡 Each node must be checked to know when to stop recursion.

Line:

if node is None:
    return acc

💡 Recursion continues to process the next binary digit.

fill_cells

Update acc with node 2's value

Shift acc left by 1 (1 << 1 = 2) and OR with node.val (0), updating acc to 2.

💡 This step appends the current node's binary digit to the accumulated number.

Line:

acc = (acc << 1) | node.val

💡 The accumulated value now represents the binary digits processed so far.

traverse

Recursive call on node 3 with acc=2

Call helper recursively on the next node (value 1) with updated acc=2.

💡 Recursion continues to the last node to complete the binary number.

Line:

return helper(node.next, acc)

💡 The recursion stack is one call away from the base case.

compare

Check base case: node 3 is not None

Confirm node 3 exists, so continue recursion.

💡 The last node is processed before hitting the base case.

Line:

if node is None:
    return acc

💡 The recursion will now process the last binary digit.

fill_cells

Update acc with node 3's value

Shift acc left by 1 (2 << 1 = 4) and OR with node.val (1), updating acc to 5.

💡 Appending the last binary digit completes the decimal conversion.

Line:

acc = (acc << 1) | node.val

💡 The accumulated value now fully represents the binary number 101 as decimal 5.

traverse

Recursive call on next node (None) with acc=5

Call helper recursively on node.next which is None, passing acc=5.

💡 This call reaches the base case, signaling recursion to unwind.

Line:

return helper(node.next, acc)

💡 The recursion has reached the end of the list.

prune

Base case reached: node is None, return acc=5

Since node is None, return the accumulated value 5 to the previous recursive call.

💡 This base case ends recursion and starts returning results back up the call stack.

Line:

if node is None:
    return acc

💡 The final decimal value is computed and ready to be returned.

reconstruct

Unwind recursion: return acc=5 through call stack

Each recursive call returns the accumulated value 5 back to its caller until the original call returns it.

💡 Unwinding recursion passes the final result back to the top-level function call.

Line:

return helper(node.next, acc)

💡 The final decimal value is propagated back to the initial function call.

reconstruct

Final step: Return decimal value 5

The getDecimalValue function returns the final decimal value 5 as the output.

💡 This final step shows the result of converting the binary linked list to an integer.

Line:

return helper(head, 0)

💡 The binary number 101 has been successfully converted to decimal 5.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getDecimalValue(head: ListNode) -> int:
    def helper(node, acc):
        # STEP 3,6,9,12: Check base case
        if node is None:
            return acc
        # STEP 4,7,10: Update acc with current node's value
        acc = (acc << 1) | node.val
        # STEP 5,8,11,13: Recursive call on next node
        return helper(node.next, acc)

    # STEP 2,14: Start recursion and return final result
    return helper(head, 0)

if __name__ == '__main__':
    node3 = ListNode(1)  # STEP 1
    node2 = ListNode(0, node3)
    node1 = ListNode(1, node2)
    print(getDecimalValue(node1))  # Output: 5

📊

Convert Binary Number in Linked List to Integer - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals how recursion and bitwise operations combine to convert a binary linked list to an integer, which is often hard to grasp from code alone.

advance

1

→

0

→

1

advance

1

→

0

→

1

Result: 0

compare

1

→

0

→

1

Result: 0

fill_cells

1

→

0

→

1

Result: 1

advance

1

→

0

→

1

Result: 1

compare

1

→

0

→

1

Result: 1

fill_cells

1

→

0

→

1

Result: 2

advance

1

→

0

→

1

Result: 2

compare

1

→

0

→

1

Result: 2

fill_cells

1

→

0

→

1

Result: 5

advance

1

→

0

→

1

Result: 5

prune

1

→

0

→

1

Result: 5

reconstruct

1

→

0

→

1

Result: 5

reconstruct

1

→

0

→

1

Result: 5

Key Takeaways

✓ The recursive approach processes each node by updating an accumulated value using bitwise operations.

This insight is hard to see from code alone because recursion and bitwise shifts happen simultaneously and are abstract.

✓ Each node's binary digit is appended to the accumulated value by shifting left and OR-ing, effectively building the decimal number.

Visualizing this shows how binary digits combine step-by-step, which is not obvious from reading the code.

✓ The base case of recursion (node is None) signals when to stop and return the final accumulated decimal value.

Understanding when recursion stops and how values return back up the call stack is clearer with stepwise visualization.

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. 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. You are given a singly linked list and need to reorder it so that the nodes are arranged in the sequence: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Store all nodes in an array, then reorder by reassigning next pointers using two pointers from ends.

B. Use a greedy approach by alternating nodes from the start and end without modifying the list structure.

C. Use dynamic programming to store intermediate reorder states and build the final list.

D. Find the middle of the list, reverse the second half, then merge the two halves alternately.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering nodes in a specific pattern without extra space overhead.

2. Step 2: Evaluate approaches for time and space

   Finding the middle, reversing the second half, and merging achieves O(n) time and O(1) space, unlike storing nodes or DP which use extra space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal approach uses middle finding and reversing [OK]

Hint: Middle + reverse + merge is classic reorder pattern [OK]

Common Mistakes:

• Thinking greedy pointer swaps suffice
• Using extra arrays unnecessarily
• Confusing DP with linked list reorder

4. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?

hard

A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates

B. No modification needed; the original in-place algorithm works correctly even with reused nodes

C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates

D. Use recursion to process nodes and detect cycles automatically

Solution

1. Step 1: Identify problem with reused nodes

   If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.

2. Step 2: Use a visited set

   Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.

3. Step 3: Why other options fail

   No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set is standard for cycle detection in linked lists [OK]

Hint: Detect cycles with visited set to avoid infinite loops [OK]

Common Mistakes:

• Assuming original algorithm handles cycles or reused nodes
• Using recursion without cycle detection

5. Suppose the problem is modified so that the linked list nodes can be reused across parts (i.e., nodes can appear in multiple parts). Which of the following changes to the algorithm correctly handles this variant?

hard

A. No changes needed; the original algorithm already supports node reuse by splitting normally.

B. Modify the algorithm to skip cutting pointers and just record start nodes for each part, allowing overlap.

C. Use a hash map to track nodes already assigned and avoid duplicates during splitting.

D. Instead of cutting the list, create new nodes for each part to allow reuse without modifying the original list.

Solution

1. Step 1: Understand node reuse requirement

   Nodes can appear in multiple parts, so original list must remain intact.

2. Step 2: Evaluate algorithm changes

   Original algorithm cuts pointers, destroying original list structure. To allow reuse, new nodes must be created for each part.

3. Step 3: Discard other options

   Skipping cutting pointers causes overlapping parts but does not create separate nodes. Hash map tracking is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Creating new nodes preserves original list and allows reuse [OK]

Hint: Node reuse requires copying nodes, not pointer cutting [OK]

Common Mistakes:

• Assuming original algorithm supports reuse
• Trying to reuse nodes without copying
• Overcomplicating with tracking structures