261. Rotate a Doubly Linked List in Groups of Given Size

A doubly linked list has n values. For every consecutive group of k nodes, left-rotate that group by one position (its first node moves to the end of that same group, and the rest shift earlier), independently for each group - including a final group with fewer than k nodes. Print the resulting sequence.

Input: The first line contains an integer n. The second line contains n space-separated integers, the doubly linked list's values. The third line contains k, the group size. Output: Print the resulting sequence after left-rotating each group of k nodes by one position, space-separated, on one line.

1 <= k <= n <= 10^5

Since this is a DOUBLY linked list, both next AND prev pointers must be correctly updated at every group boundary - forgetting to update prev pointers (easy to do if focused only on next-pointer relinking) would leave the list's backward links broken.

For every consecutive group of k nodes in a doubly linked list, left-rotate that group by one position, independently. Brute force: Copy all values into an array, rotate each k-sized chunk of the array by 1, and rebuild the list - this works but uses O(n) extra space, when each chunk can be rotated directly using its own existing nodes. Optimised: Applying a small, targeted relink (move just the first node of each chunk to that chunk's end, rather than a full chunk reversal) achieves the group-wise rotation directly on existing nodes - similar in spirit to 'Reverse in Groups of Size K' but with a lighter-touch relinking operation per group.

Traverse the doubly linked list once to copy all values into an array, then process the array in chunks of size k (the last chunk may be shorter), left-rotating each chunk by one position using a temporary copy of that chunk, and finally rebuild a brand-new doubly linked list from the fully rotated array. This is correct because array rotation of each fixed-size block is straightforward to get right using a scratch buffer, but it pays the cost of two full extra passes worth of memory: one for the array copy and one for the temporary chunk buffers, plus rebuilding the list from scratch. Time: O(n) Space: O(n)

Iterate through the list once with plain pointers: for each group, remember the node just before the group and the group's first node, advance a pointer k nodes forward within the group (stopping early if the list runs out for the final group), then relink just four next/prev pointers to move the group's first node to the position right after the group's last node, before moving on to the next group. This is correct for the same reason as the recursive version, but replacing recursion with an explicit loop means no call stack is consumed and no auxiliary array is ever created, achieving the rotation with only a constant amount of extra bookkeeping. Time: O(n) Space: O(1)

Process the list recursively: for each call, walk k nodes forward (or fewer for the final group) to find the group's boundary, detach the group's first node and relink it after the group's last node using pointer surgery, then recurse on the remainder of the list starting after this group. This is correct because rotating one group by one position only requires moving its first node to its end, and doing this independently for each group and recursing on the rest handles the whole list correctly, but every recursive call adds a stack frame, so memory grows with the number of groups rather than staying constant. Time: O(n) Space: O(n/k)

1. Process the list k nodes at a time, exactly like reversing in groups, except within each group you only move the FIRST node to that group's END (a rotation-by-1, not a full reversal). 2. A group of size 1 (which can happen in a shorter trailing group) is completely unaffected by a rotate-by-1. 3. Keep BOTH next and prev pointers correctly updated at every group boundary, since this is a doubly linked list.

Time: O(n) - every node's pointers are touched a bounded number of times across the whole process. Space: O(1) extra space beyond a few pointer variables per group boundary.

k = 1, where a group of size one is unaffected by a one-position rotation (per the hints); k = n (a single group spanning the whole list); a trailing partial group shorter than k.

Be ready to contrast this clearly with 'Reverse a Linked List in Groups of Size K' - rotation-by-1 within a group is a much LIGHTER operation than a full reversal, even though both problems share the same 'process k nodes at a time' outer structure.