259. Rotate a Doubly Linked List by N Nodes

A doubly 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 doubly linked 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 in order, space-separated.

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

This is the doubly linked list version of 'Rotate a Linked List by N Nodes' - the core algorithm is identical, but every pointer relink must be mirrored in the prev direction too, unlike the singly linked version.

Rotate a doubly linked list left by n positions, moving the first n nodes to the end. Brute force: Copy all values into an array, rotate the array, and rebuild the doubly linked list from scratch, setting up all next/prev pointers fresh - this works but discards the existing nodes unnecessarily. Optimised: Relinking just a handful of pointers (in BOTH directions, since it's doubly linked) achieves the rotation directly on the existing nodes - having both next and prev pointers doesn't change the algorithm's overall SHAPE versus a singly linked list, it just means every relink must be done consistently in both directions.

Traverse forward exactly n steps from the head to find the node that will become the new tail (the nth node), and note its next node as the new head. Then relink in place: connect the old tail's next pointer to the old head, set the old head's prev to the old tail, set the new head's prev to null, and set the new tail's next to null. This performs the rotation with a single traversal up to position n and a constant number of pointer updates, needing no extra array or new node allocation at all. Time: O(length) Space: O(1)

Traverse the doubly linked list once, copying all values into an array. Build a new array that is the rotation of the original by n positions (elements from index n onward, followed by the first n elements). Then rebuild a fresh doubly linked list from this rotated array. This does the rotation in a single pass over the data instead of n repeated traversals, at the cost of needing extra space to hold the values. Time: O(length) Space: O(length)

Repeatedly perform a 'rotate by 1' operation n times: each time, traverse from the head all the way to the tail (since no tail pointer is maintained), detach the head node, and reattach it after the current tail. Doing this n times, each requiring a full traversal to locate the tail, correctly produces the rotated list but repeats the same traversal work over and over. Time: O(n * length) Space: O(1)

1. Find what will become the NEW head (the (n+1)th node) and the NEW tail (the OLD nth node). 2. Connect the old tail's next to the old head, AND the old head's prev to the old tail (both directions, since this is doubly linked). 3. Break the link between the old nth and (n+1)th nodes, in BOTH directions.

Time: O(n) - walking to find the relevant positions. Space: O(1) extra space - pointers relinked in place.

n = 0 (list unchanged), n equal to the list's length (list unchanged after a full rotation), and a list of length 1.

Be ready to explicitly double-check that EVERY relink is applied in BOTH directions (next AND prev) - forgetting to update one direction is the most common bug when adapting singly linked list algorithms to doubly linked lists.