Create a dummy node before head to simplify edge cases. Initialize less_tail and prev to dummy, current to head (node with value 1).
💡 Dummy node helps easily insert nodes at the start without special cases. less_tail tracks the end of the less-than-x partition.
Line:dummy = ListNode(0)
dummy.next = head
less_tail = dummy
prev = dummy
current = head
💡 Setting up dummy and pointers prepares for in-place rearrangement while preserving original list structure.
compare
Check current node value 1 < x=3
Current node value 1 is less than x. Since less_tail.next == current, move less_tail and prev forward to current, then advance current.
💡 When current is immediately after less_tail, just extend the less-than-x partition by moving pointers forward.
Line:if current.val < x:
if less_tail.next == current:
less_tail = less_tail.next
prev = current
current = current.next
💡 Nodes already in correct position extend the less-than-x partition without rearrangement.
compare
Check current node value 4 >= x=3
Current node value 4 is not less than x, so move prev and current forward without changing less_tail.
💡 Nodes greater or equal to x remain in place; just advance pointers to continue traversal.
Line:else:
prev = current
current = current.next
💡 Nodes >= x are skipped for repositioning but traversal continues.
compare
Check current node value 3 >= x=3
Current node value 3 equals x, so again move prev and current forward without repositioning.
💡 Nodes equal to x are treated like greater nodes and remain in place.
Line:else:
prev = current
current = current.next
💡 Traversal continues without changes for nodes >= x.
insert
Current node value 2 < x=3, reposition needed
Current node value 2 is less than x but not immediately after less_tail. Remove current from its place and insert after less_tail.
💡 This step moves a node less than x forward to maintain partition order.
Line:prev.next = current.next
current.next = less_tail.next
less_tail.next = current
less_tail = current
current = prev.next
💡 Repositioning nodes less than x maintains relative order and partitions list in-place.
advance
Current node value 5 >= x=3, advance pointers
Current node value 5 is not less than x, so move prev and current forward without repositioning.
💡 Nodes >= x remain in place; traversal continues.
Line:else:
prev = current
current = current.next
💡 Traversal continues through nodes >= x without changes.
insert
Current node value 2 < x=3, reposition needed
Current node value 2 is less than x and not immediately after less_tail. Remove current and insert after less_tail.
💡 Another repositioning to maintain partition order and relative order of less-than-x nodes.
Line:prev.next = current.next
current.next = less_tail.next
less_tail.next = current
less_tail = current
current = prev.next
💡 In-place repositioning preserves order and partitions list correctly.
traverse
Traversal complete, current is null
Current pointer reached null, indicating end of list traversal. Partitioning is complete.
💡 Traversal ends when current is null, meaning all nodes have been processed.
Line:while current:
...
return dummy.next
💡 All nodes have been examined and repositioned as needed.
reconstruct
Return new head of partitioned list
Return dummy.next as the head of the rearranged list, which starts at node with value 1.
💡 Dummy.next points to the start of the partitioned list, skipping the dummy node.
Line:return dummy.next
💡 The partitioned list head is correctly updated after rearrangement.
reconstruct
Final list order verified
The final linked list order is [1, 2, 2, 4, 3, 5], correctly partitioned around x=3 with relative order preserved.
💡 This confirms the algorithm's correctness and in-place rearrangement.
💡 Partitioning is successful without extra lists, preserving order and list integrity.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def partition(head, x):
if not head:
return None
dummy = ListNode(0) # STEP 1
dummy.next = head
less_tail = dummy
prev = dummy
current = head
while current: # STEP 2-8
if current.val < x:
if less_tail.next == current:
less_tail = less_tail.next # STEP 2
prev = current
current = current.next
else:
prev.next = current.next # STEP 5 & 7
current.next = less_tail.next
less_tail.next = current
less_tail = current
current = prev.next
else:
prev = current # STEP 3,4,6
current = current.next
return dummy.next # STEP 9
# Driver code
if __name__ == '__main__':
nodes = [1,4,3,2,5,2]
dummy = ListNode(0)
curr = dummy
for v in nodes:
curr.next = ListNode(v)
curr = curr.next
new_head = partition(dummy.next, 3)
curr = new_head
res = []
while curr:
res.append(curr.val)
curr = curr.next
print(res) # Expected: [1,2,2,4,3,5]
📊
Partition List Around Value X - Watch the Algorithm Execute, Step by Step
Watching each pointer move and node rearrangement live helps you understand how the algorithm maintains list integrity while partitioning without extra space.
Step 1/10
·Active fill★Answer cell
setup
0
→
1
→
4
→
3
→
2
→
5
→
2
advance
0
→
1
→
4
→
3
→
2
→
5
→
2
advance
0
→
1
→
4
→
3
→
2
→
5
→
2
advance
0
→
1
→
4
→
3
→
2
→
5
→
2
insert
0
→
1
→
4
→
3
→
2
→
5
→
2
advance
0
→
1
→
4
→
3
→
2
→
5
→
2
insert
0
→
1
→
4
→
3
→
2
→
5
→
2
traverse
0
→
1
→
4
→
3
→
2
→
5
→
2
reconstruct
1
→
2
→
2
→
4
→
3
→
5
final
1
→
2
→
2
→
4
→
3
→
5
Result: [1, 2, 2, 4, 3, 5]
Key Takeaways
✓ In-place partitioning can be done by carefully repositioning nodes less than x without extra lists.
This insight is hard to see from code alone because pointer manipulations are subtle and easy to miss.
✓ Maintaining a less_tail pointer allows efficient insertion of nodes less than x while preserving relative order.
Visualizing less_tail movement clarifies how the partition boundary advances.
✓ When current node is immediately after less_tail, no repositioning is needed, simplifying pointer updates.
This condition avoids unnecessary node moves and keeps the algorithm efficient.
Practice
(1/5)
1. 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
Step 1: Trace addAtHead(1)
List: dummy -> 1; size=1; tail points to node with val=1.
Step 2: Trace addAtTail(3)
List: dummy -> 1 -> 3; size=2; tail points to node with val=3.
Step 3: Trace addAtIndex(1, 2)
Insert 2 at index 1: dummy -> 1 -> 2 -> 3; size=3; tail remains at 3.
Step 4: Trace get(1)
Index 1 corresponds to node with val=2.
Final Answer:
Option A -> Option A
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
2. 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
3. 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
Step 1: Identify operation steps
addAtTail uses the tail pointer to append a new node directly without traversal.
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.
Final Answer:
Option C -> Option C
Quick Check:
Tail pointer eliminates traversal, so addAtTail is constant time [OK]
4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?
medium
A. O(n) -- recursion stack uses space proportional to list length
B. O(1) -- only constant extra pointers used
C. O(log n) -- recursion depth is halved each call
D. O(n^2) -- due to repeated pointer updates in recursion
Solution
Step 1: Identify recursion depth
The helper function recurses once per node, so recursion depth is n.
Step 2: Calculate space usage
Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.
Final Answer:
Option A -> Option A
Quick Check:
Recursion stack proportional to list length [OK]
Hint: Recursion depth equals list length -> O(n) space [OK]
Common Mistakes:
Assuming constant space due to in-place changes
Confusing recursion depth with log n
Overestimating to quadratic space
5. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?
hard
A. Reject negative indices as invalid to keep implementation simple and efficient.
B. Traverse from tail backwards for negative indices to achieve O(1) access.
C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.
D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.
Solution
Step 1: Understand negative index semantics
Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).
Step 2: Implement index normalization
Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.
Step 3: Evaluate alternatives
Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.
Final Answer:
Option D -> Option D
Quick Check:
Index normalization preserves existing complexity and correctness [OK]
Hint: Normalize negative indices by adding size before operation [OK]
Common Mistakes:
Trying backward traversal in singly linked list
Switching to doubly linked list unnecessarily
Ignoring negative indices
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.