253. Deletion From a Circular Linked List

A circular singly linked list has n node values (its last node's next pointer points back to the first node). Delete the node at 0-indexed position k and print the remaining n-1 values, starting from the list's head (the original head, unless it was the node deleted, in which case the following node becomes the new head).

Input: The first line contains an integer n. The second line contains n space-separated integers, the circular list's values starting from the head. The third line contains k, the 0-indexed position to delete. Output: Print the remaining n-1 values, space-separated, starting from the (possibly new) head.

2 <= n <= 10^5, 0 <= k < n

The WRAPAROUND detail (position 0's predecessor is the LAST node, not undefined or null) is the single most important thing to get right here - forgetting this wraparound is the most common source of bugs when adapting singly-linked-list deletion logic to a circular list.

Delete a specific node (by position) from a circular linked list. Brute force: Copy all values except the one at position k into a new array and rebuild the circular list from scratch - this works but discards all the existing nodes unnecessarily, when a simple relink of just the predecessor's pointer achieves the deletion directly. Optimised: Since a circular list has no 'null' boundary to worry about, finding the correct predecessor (accounting for the WRAPAROUND at position 0) and relinking just ONE pointer is all that's needed - no rebuilding, no extra array, and the remaining nodes automatically keep their original relative order.

Since k is already known upfront, walk directly from the head for k steps while keeping a trailing 'previous' pointer, and as soon as the node at position k is reached, unlink it in that same pass by setting previous.next to the target's next (or, if k is 0, simply move the head reference to the second node and fix the last node's next pointer to point at the new head). This combines locating and deleting into one traversal with no pre-counting or auxiliary storage, handling the head-deletion edge case inline, and then a single subsequent pass prints the remaining n-1 values starting from the possibly new head. Time: O(n) Space: O(1)

Traverse the circular linked list once, starting at the head, collecting all n node values into a plain array (stopping when you loop back to the head), then remove the element at index k from that array, and finally build a brand-new circular linked list from the remaining n-1 values. This is simple to reason about because it reduces the problem to ordinary array deletion, but it does unnecessary extra work allocating an entirely new list and array instead of just unlinking one node from the existing structure. Time: O(n) Space: O(n)

First traverse the circular list to confirm its structure and locate the node at position k together with its predecessor by walking node-to-node with a counter (no array involved), then, as a conceptually separate step, unlink the target node by pointing its predecessor's next pointer at the node after it (updating the head reference if the head itself was deleted). This avoids the brute force's array allocation entirely, operating directly on the existing nodes, but still treats locating and unlinking as two distinct traversal concerns. Time: O(n) Space: O(1) extra

1. Find the node just BEFORE position k, remembering the list WRAPS AROUND - so position 0's predecessor is the LAST node, not 'nothing'. 2. Relink that predecessor's 'next' pointer to skip directly over the node being deleted. 3. If deleting the HEAD itself (position 0), update the head pointer to the FOLLOWING node before relinking.

Time: O(n) in the worst case, to walk to the node just before position k (or O(k) if walking directly from the head). Space: O(1) extra space - just a couple of pointer variables.

k = 0, deleting the head itself so the head pointer must move to the next node (per the hints); k = n-1, deleting the last node whose next wraps back to the head; the minimum n = 2, deleting one of only two nodes.

Be ready to explain the special case of deleting the HEAD explicitly - since the 'head' isn't a fixed structural position in a circular list (any node conceptually could be called 'the head'), care must be taken to correctly update whatever your program uses as its head reference.