Practice
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head or not head.next:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
res.append(curr.val)
curr = curr.next
print(res)Solution
Step 1: Trace first iteration of while loop
odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.Step 2: Loop ends as even.next is null; link odd.next to even_head (2)
Final list order: 1 -> 3 -> 2 -> 4.Final Answer:
Option B -> Option BQuick Check:
Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]
- Confusing node values with indices
- Off-by-one errors in pointer updates
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
def helper(front, back):
if not back:
return True
if not helper(front, back.next):
return False
if front[0] == back or front[0].next == back:
back.next = None
return False
tmp = front[0].next
front[0].next = back
back.next = tmp
front[0] = tmp
return True
helper([head], head)
n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
print(curr.val, end=' ')
curr = curr.next
Solution
Step 1: Trace helper calls with input 1->2->3
Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.Step 2: Verify final list traversal output
Prints nodes in order: 1 3 2, confirming correct reorder.Final Answer:
Option C -> Option CQuick Check:
Output matches reorder pattern for 3 nodes [OK]
- Assuming no reorder happens
- Stopping recursion too early
- Misplacing next pointers
k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?Solution
Step 1: Calculate total nodes and part sizes
Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.Step 2: Assign nodes to parts
Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].Final Answer:
Option B -> Option BQuick Check:
Sum of parts equals original list length and sizes differ by at most one [OK]
- Assigning remainder nodes to last parts
- Off-by-one in part sizes
- Returning fewer than k parts
class BrowserHistory:
def __init__(self, homepage: str):
self.back_stack = [homepage]
self.forward_stack = []
def visit(self, url: str) -> None:
self.back_stack.append(url)
# Missing forward_stack.clear() here
def back(self, steps: int) -> str:
while steps > 0 and len(self.back_stack) > 1:
self.forward_stack.append(self.back_stack.pop())
steps -= 1
return self.back_stack[-1]
def forward(self, steps: int) -> str:
while steps > 0 and self.forward_stack:
self.back_stack.append(self.forward_stack.pop())
steps -= 1
return self.back_stack[-1]
Solution
Step 1: Identify visit method behavior
Visit appends new URL but does not clear forward_stack, so forward history remains outdated.Step 2: Understand impact on forward navigation
Without clearing forward_stack, forward() returns stale pages that should have been discarded.Final Answer:
Option B -> Option BQuick Check:
Clearing forward_stack on visit is essential to maintain correct forward history [OK]
- Forgetting to clear forward stack on visit
- Incorrectly popping from back stack
- Mismanaging stack boundaries
k parts:Solution
Step 1: Analyze pointer advancement
Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.Step 2: Identify potential error
If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.Final Answer:
Option A -> Option AQuick Check:
Missing None check before curr = curr.next causes runtime error [OK]
- Forgetting None check before pointer advance
- Incorrectly cutting list by setting next to None too early
- Misusing dummy heads
