Skip to main content

Reverse a Doubly Linked List

Problem Statement:​

Given a doubly linked list. Your task is to reverse the doubly linked list and return its head.

Examples:

Input:LinkedList: 3 <-> 4 <-> 5
Output:5 <-> 4 <-> 3

Input:LinkedList: 75 <-> 122 <-> 59 <-> 196
Output:196 <-> 59 <-> 122 <-> 75

Expected Time Complexity: O(n).

  • Example:

✅ Solution: In-Place Reversal of Doubly Linked List​

/*
class DLLNode {
  public:
    int data;
    DLLNode *next;
    DLLNode *prev;

    DLLNode(int val) {
        data = val;
        this->next = NULL;
        this->prev = NULL;
    }
};
*/

class Solution {
  public:
    // Function to reverse a doubly linked list
    DLLNode* reverseDLL(DLLNode* head) {
        if(head == NULL || head->next == NULL) return head;

        DLLNode* curr = head;
        DLLNode* prevNode = NULL;

        while(curr != NULL){
            prevNode = curr->prev;      // Store previous
            curr->prev = curr->next;    // Swap next and prev
            curr->next = prevNode;      // Move forward
            curr = curr->prev;          // Continue in swapped direction
        }

        // Return new head (prev of last non-null curr)
        return prevNode->prev;
    }
};

📝 How It Works​

  • Start from the head of the DLL.
  • At each node, swap its next and prev pointers.
  • After the loop ends, curr becomes NULL, and prevNode will point to the last node processed.
  • The new head is at prevNode->prev.

🧩 Key Swap Logic​

curr->prev = curr->next;
curr->next = prevNode;

This inverts the direction of the list.

⏱️ Time & Space Complexity​

OperationTimeSpace
ReversalO(N)O(1)

⚠️ Edge Cases​

  • Empty list → returns NULL
  • Single node → returns the node as-is
  • List with even/odd number of nodes

💡 Other Approaches​

  • Using stack: Push nodes into stack and re-link from top — uses O(N) space.
  • Recursive reversal: Elegant, but not space-efficient due to recursion stack.

🔁 Related Problems​

  • Reverse a singly linked list
  • Flatten a multilevel doubly linked list
  • Rotate DLL by k nodes
  • Check if DLL is palindrome
💬

Discussion & Doubts