97. Rotate a Linked List by N Nodes

A singly linked list has values given in order. Rotate it left by n nodes (the first n nodes move, in order, to the end of the list) and print the result.

Input: The first line contains the list's length. The second line contains that many space-separated integers, the list's values in order. The third line contains n, the number of nodes to rotate left by. Output: Print the rotated list's values, space-separated, on one line.

1 <= list length <= 10^5, 0 <= n <= list length

This is the general version of 'Move the Last Element to the Front' - that problem is exactly this one with n fixed at (list length - 1), a nice illustration of a specific problem being a special case of a more general technique.

Rotate a linked list left by n positions, moving the first n nodes (in order) to the end. Brute force: Copy all values into an array, rotate the array (slice and rearrange), and rebuild the list from scratch - this works but discards and reallocates all the existing nodes unnecessarily. Optimised: Since rotation only requires relinking THREE specific pointers (finding the new head, connecting the old tail to the old head, and cutting after the nth node), the existing nodes can simply be relinked in place - no new allocation, and the whole operation costs just two passes (one to find positions, one implicit in relinking).

Rotate the list left by exactly one node, n separate times: each single rotation removes the current head, traverses all the way to the end of the list, and appends the removed node there as the new tail. Repeating this basic single-step rotation n times produces the same result as rotating by n directly, but every single-step rotation requires its own full traversal to the end of the list, so the total work multiplies out badly when both the list length and n are large. Time: O(n * L), where L is the list length Space: O(1)

Traverse the list once to find both the current tail and the node at position n (which will become the new tail) and the node right after it (which will become the new head). Then simply relink the current tail's next pointer to the old head, and set the node at position n's next pointer to null, immediately producing the rotated list. This achieves the rotation using only pointer reassignment on the existing nodes, with a single traversal and no auxiliary array or new node allocation at all, making it strictly better in space than the array-rebuild approach while matching its linear time. Time: O(L) Space: O(1)

Traverse the list once to copy all L values into an array, then construct the rotated sequence by concatenating the sub-array from index n to L-1 with the sub-array from index 0 to n-1, and finally build a brand-new linked list from this reordered array. This avoids the repeated end-of-list traversals of the brute-force approach, doing the whole rotation in a single pass over the data, but at the cost of extra memory for the intermediate array and for allocating an entirely new set of list nodes. Time: O(L) Space: O(L)

1. Walk to the (n+1)th node - this becomes the NEW head. 2. Connect the OLD tail's next pointer to the OLD head (closing the rotation). 3. Cut the link right after the nth node (which is now the new tail of the 'moved to the back' segment).

Time: O(n) - proportional to the list's length, to walk to the relevant positions. Space: O(1) extra space - pointers are relinked in place.

n = 0 or n equal to the list's length, both of which leave the list unchanged (per the hints); a single-node list; list length up to 10^5 for performance.

Be ready to handle n equal to 0 or the full list length as a no-op edge case - rotating by the list's own length (or by 0) leaves the list completely unchanged.