254. Reverse a Doubly Linked List

A doubly linked list is given as its n node values in order. Print the values in reverse order.

Input: The first line contains an integer n. The second line contains n space-separated integers, the doubly linked list's values in order. Output: Print the values in reverse order, space-separated.

1 <= n <= 10^5

This is a great example of how having EXTRA structure (the prev pointers) can make an operation strictly EASIER, not just possible in a different way - always consider what a richer data structure already gives you for free.

Reverse a doubly linked list, so the last node becomes the first. Brute force: Copy all values into an array, reverse the array, and build an entirely new doubly linked list from it - this works but discards the existing nodes and their already-present backward links unnecessarily. Optimised: Since a doubly linked list ALREADY has backward (prev) links, reversing it is simply a matter of SWAPPING each node's next and prev pointers (rather than needing a three-pointer relinking dance like a singly linked list) - a much simpler operation, needing no extra list or array at all.

Traverse the doubly linked list forward from head to tail, copying every value into an array in the order encountered. Then simply print the array's values starting from the last index down to the first, producing the reversed order. The original list's pointers are never touched at all - all the work happens on the copied array. Time: O(n) Space: O(n)

Traverse the list forward using only the next pointers, pushing each value onto an explicit stack as it's visited. Once the traversal reaches the end, pop every value off the stack one at a time and print it - since a stack is last-in-first-out, popping naturally yields the values in reverse order. This models the reversal as an explicit LIFO structure rather than relying on random access into an array. Time: O(n) Space: O(n)

Traverse the doubly linked list once, and at each node simply swap its next and prev pointers with each other. Once every node has been processed this way, the node that used to be the tail becomes the new head (since its former prev, now its next, leads back through the list), and following the new next pointers from there naturally visits the nodes in reverse of their original order. This exploits the fact that a doubly linked list already stores both directions of traversal, requiring no auxiliary array or stack at all. Time: O(n) Space: O(1) extra

1. Walk the list once, and at EVERY node, swap its next and prev pointers. 2. Once done, set the new head to whatever used to be the TAIL.

Time: O(n) - one single pass through the list, swapping two pointers per node. Space: O(1) extra space - no new list or array needed.

n = 1 (the list is unchanged), and n = 10^5 for performance.

Be ready to contrast this directly with reversing a SINGLY linked list - the doubly linked version is genuinely simpler precisely because the backward links already exist and just need to be swapped into the forward role.