💡 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.
Step 1/14
·Active fill★Answer cell
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/5)
1. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child list may also have one or more children of its own, and so on, creating a multilevel data structure. Which approach guarantees an optimal solution to flatten this multilevel doubly linked list into a single-level doubly linked list preserving the original order?
easy
A. Use a recursive depth-first traversal that returns the tail of each flattened child list and connects it back to the parent list.
B. Use a breadth-first traversal with a queue to process nodes level by level, appending child lists at the end of the current level.
C. Iteratively traverse the list, and whenever a node has a child, find the tail of the child list and splice it between the current node and its next node, updating all pointers in-place without extra space.
D. Apply a greedy approach that always flattens the child list with the largest number of nodes first to minimize pointer updates.
Solution
Step 1: Understand the problem structure
The problem requires flattening a multilevel doubly linked list into a single-level list while preserving the order of nodes as they appear in depth-first traversal.
Step 2: Evaluate approaches
Recursive DFS (A) works but uses extra stack space. The in-place iterative approach (B) efficiently flattens by splicing child lists without extra space. BFS (C) changes order and is not optimal. Greedy (D) does not guarantee correct order.
Final Answer:
Option C -> Option C
Quick Check:
In-place iterative flattening preserves order and uses O(1) extra space [OK]
Hint: In-place iterative splicing preserves order and uses no extra space [OK]
Common Mistakes:
Confusing BFS with DFS order
Assuming recursion is always optimal
Thinking greedy approach reduces pointer updates
2. You are given a singly linked list and asked to reorder it so that all nodes at odd indices appear before nodes at even indices, preserving the relative order within each group. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Using a stack to push odd nodes and then pop them to reorder the list
B. Sorting the list based on node values and then merging odd and even indexed nodes
C. Using two pointers to rearrange nodes in-place by linking odd and even nodes separately and then concatenating
D. Using a hash map to store nodes by index parity and reconstructing the list from the map
Solution
Step 1: Understand problem constraints
The problem requires reordering nodes by their position (odd/even indices) without extra space and in linear time.
Step 2: Evaluate approaches
Only the two-pointer in-place rearrangement achieves O(n) time and O(1) space by relinking nodes without extra data structures.
Final Answer:
Option C -> Option C
Quick Check:
Two-pointer approach is standard for odd-even linked list rearrangement [OK]
Hint: Two pointers rearranging nodes in-place is optimal [OK]
Common Mistakes:
Thinking sorting or extra data structures are needed
Assuming extra space is acceptable for optimal
3. 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
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.
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.
Final Answer:
Option C -> Option C
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
4. What is the space complexity of the optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?
medium
A. O(n) due to storing copied nodes in a hash map
B. O(n) because each node's random pointer requires extra space
C. O(n) due to recursion stack in the copying process
D. O(1) because no extra data structures are used besides new nodes
Solution
Step 1: Identify auxiliary space usage
The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.
Step 2: Confirm space complexity
Only new nodes are created, which is required output space, so auxiliary space is O(1).
Final Answer:
Option D -> Option D
Quick Check:
No extra data structures or recursion stack used [OK]
Hint: Weaving nodes avoids extra mapping space [OK]
Common Mistakes:
Confusing output space with auxiliary space
Assuming recursion is used and adds stack space
Thinking random pointers require extra space
5. 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
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).
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).
Final Answer:
Option A -> Option A
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)
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.