← 返回 anthropic 的题目列表Thread-Safe Linked List Task Queue Transformation
类型：online_judge
Problem: Thread-Safe Linked List Task Queue Transformation (Linked List + Concurrency Discussion)
You maintain a task queue as a singly linked list:
Node {
int taskId;
Node* next;
}
Perform a batch transformation: split the list into consecutive groups of size k and reverse nodes within each group. If the last group has fewer than k nodes, keep it unchanged.
Requirements
Implement reverseKGroup(head, k) and return the new head.
Provide at least 5 test cases covering key edge cases.
Discuss how to do this safely in a multi-threaded environment:
Other threads may read the queue concurrently (read-only) or append to the tail.
Would you use a global lock, RW lock, segmented locks, or copy-on-write? Explain tradeoffs.
Constraints
0 <= n <= 2e5
1 <= k <= 1e5
Expected O(n) time and O(1) extra space (excluding tests)
Example
Input: 1->2->3->4->5, k=2 Output: 2->1->4->3->5
Example
Input
list=1 2 3 4 5
k=2
Output
2 1 4 3 5