A queue of patients is stored as a singly linked list of n token numbers. The doctor calls the k-th patient from the end. Remove that node, using a single pass over the list, and print the remaining tokens front to back. If none remain, print empty.
Constraints
- 1 ≤ k ≤ n ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n integers. Line 3: k.
- Output
- The remaining values space-separated, or `empty`.
Examples
Input 1
5
4 8 15 16 23
2Output
4 8 15 23The 2nd from the end is 16.
Input 2
1
9
1Output
emptyRemoving the only node leaves an empty list.
Show hints
- Move a "lead" pointer k steps ahead first.
- Then move both pointers together; when the lead reaches the end, the trailing pointer is just before the node to remove.
Show the explanation
Use two pointers with a gap of k. Start both at a dummy node, move lead k + 1 steps ahead, then advance both until lead falls off the end. The trailing pointer now sits just before the k-th node from the end, so trail.next = trail.next.next removes it. The dummy node makes removing the head (k = n) work like any other case.
Original UniCircle question. Last reviewed 22 Oct 2026.