In data structures, how would you reverse a doubly linked list in place so that the first node becomes the last and the last node becomes the first?

Introduction / Context:
Reversing a doubly linked list is a classic interview problem that checks your understanding of pointer manipulation, list traversal, and in place algorithms. Unlike singly linked lists, doubly linked lists have both next and prev pointers, which makes reversing conceptually simple but still requires careful handling to avoid breaking links or losing track of the head and tail. This question asks for an in place method, meaning you are expected to modify existing nodes rather than allocate new ones.

Given Data / Assumptions:

• The data structure is a doubly linked list with next and prev pointers in each node.
• The list may be empty, have one node, or have many nodes.
• You want to reverse the order of nodes so that traversal from the new head visits nodes in the original reverse order.
• The solution should be in place, using O(1) extra space and O(n) time.
• Pointer integrity must be maintained at all times.

Concept / Approach:
In a doubly linked list, each node has two references: next (to the next node) and prev (to the previous node). When reversing the list, we can exploit this structure directly. If we traverse the list node by node and for each node swap its next and prev pointers, then the direction of all links becomes reversed. After finishing this traversal, the last processed node will be the new head of the list. This idea leads to a clean in place algorithm: walk through the list, swapping pointers, and track the last node visited. There is no need to copy data into auxiliary storage or create new nodes.

Step-by-Step Solution:
Step 1: Handle edge cases. If the head pointer is NULL or there is only a single node, return the head as is because the list is already trivially reversed. Step 2: Initialize a current pointer to head and a temporary pointer temp set to NULL. Also prepare a variable new_head which will later store the last processed node. Step 3: While current is not NULL, perform the following actions for each node: set temp = current.prev, then assign current.prev = current.next, and assign current.next = temp. This swaps the two pointers. Step 4: After swapping, move current to current.prev, because the swap has reversed the direction of pointers and the original next is now stored in prev. Step 5: Keep updating new_head to the last non NULL node visited. When the loop ends, new_head will point to the original tail, which is now the head of the reversed list. Return new_head as the new head pointer.

Verification / Alternative check:
To verify correctness, you can consider a small example with three nodes A, B, and C. Initially, A.next = B, B.next = C, and C.next = NULL, with corresponding prev pointers. After swapping next and prev in each node and then adjusting the head, you should see that C becomes the new head, C.next = B, B.next = A, and A.next = NULL, with prev pointers reversed accordingly. The algorithm touches each node exactly once and performs a constant amount of pointer work per node, confirming O(n) time and O(1) extra space. An alternative solution might copy nodes into an array and rebuild the list, but that uses extra memory and is not truly in place.

Why Other Options Are Wrong:
Option B is functionally correct but violates the in place requirement by copying all nodes into an array and reconstructing the list using additional space. Option C unnecessarily deletes and re inserts nodes, which is complex and error prone. Option D only reverses the data values in the nodes, not the node order itself, so the list structure is not truly reversed. Option E confuses sorting with reversing; sorting changes the order based on key values, which might be completely different from the original reverse order.

Common Pitfalls:
A common pitfall is forgetting to update the head pointer to the new head at the end of the process. Another mistake is moving current to current.next instead of current.prev after swapping pointers, which can cause an infinite loop or skipped nodes because the meaning of the pointers changes mid iteration. Some implementations also forget to handle empty or single node lists gracefully. Being systematic about pointer updates and walking through a small example mentally helps avoid these issues.

Final Answer:
To reverse a doubly linked list in place, traverse the list once and for each node swap its next and prev pointers, and when the traversal finishes, set the head pointer to the last processed node, which becomes the new head of the reversed list.