Reverse a Doubly Linked List

Slug: reverse-a-doubly-linked-list

Difficulty: Easy

Id: 700137

Topic Tags: doubly-linked-list, Linked List, Data Structures

Company Tags: D-E-Shaw, Adobe

Summary

Given a doubly linked list (DLL), the task is to reverse the DLL. A doubly linked list has nodes with two pointers - one pointing to the next node and another pointing to the previous node.

Detailed Explanation

To solve this problem, we can follow these steps:

Start from the head of the list.
Store the current node in a temporary variable.
Move the current pointer to the next node (i.e., curr = curr->next;).
Update the prev and next pointers for the stored node (stored->prev = curr; stored->next = curr->next; curr->next = stored;).
Repeat steps 2-4 until we reach the end of the list.
At the end, update the head pointer to point to the new first node (i.e., head = stored;).

This algorithm has a time complexity of O(n), where n is the number of nodes in the DLL, and a space complexity of O(1) as we only use a few extra variables.

Here's an ASCII art diagram of the process:

   +-------+       +-------+
   |  A  | --> |  B  | --> ... --> Z
   +-------+       +-------+

  (initial list)

   +-------+       +-------+
   |  Z  | <-- | Y  | <-- ... <-- A
   +-------+       +-------+

  (reversed list)

Optimized Solutions

Java

class Node { int data; Node prev, next; public Node(int data) { this.data = data; this.prev = null; this.next = null; } } public class Main { public static Node reverse(Node head) { Node prev = null; Node curr = head; while (curr != null) { Node stored = curr; curr = curr.next; stored.prev = curr; stored.next = prev; prev = stored; } return prev; } public static void main(String[] args) { // Example usage Node head = new Node(1); head.next = new Node(2); head.next.prev = head; head.next.next = new Node(3); head.next.next.prev = head.next; Node reversedHead = reverse(head); } }