Reverse a Doubly Linked List in DSA C

Mental Model

We flip the direction of each link between nodes so the list goes backward instead of forward.

Analogy: Imagine a train where each carriage can connect to the one before and after. Reversing the train means swapping these connections so the last carriage becomes the first.

null ← 1 ↔ 2 ↔ 3 -> null
↑ head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, reverse the list

Goal: Change the list so it reads 3 ↔ 2 ↔ 1 instead of 1 ↔ 2 ↔ 3

Step 1: Start at head (node 1), swap its prev and next pointers

null ← 1 [prev=null, next=2] -> null
After swap: null ← 1 [prev=2, next=null] -> null
Head at 1

Why: Swapping pointers reverses the direction of links for this node

Step 2: Move to next node using old next pointer (node 2), swap its prev and next

null ← 1 ← 2 -> 3 -> null
After swap: null ← 1 ← 2 [prev=3, next=1] -> null
Head at 1

Why: Continue reversing links for each node

Step 3: Move to next node (node 3), swap its prev and next

null ← 1 ← 2 ← 3 -> null
After swap: null ← 1 ← 2 ← 3 [prev=null, next=2] -> null
Head at 1

Why: Last node's pointers swapped, reversing its links

Step 4: Update head to last processed node (node 3)

null ← 3 ↔ 2 ↔ 1 -> null
↑ head

Why: New head is the old tail after reversal

Result:

null ← 3 ↔ 2 ↔ 1 -> null
Head points to node 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Append node at end
void append(Node** head_ref, int data) {
    Node* newNode = createNode(data);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Reverse the doubly linked list
void reverse(Node** head_ref) {
    Node* curr = *head_ref;
    Node* temp = NULL;

    while (curr != NULL) {
        // Swap prev and next pointers
        temp = curr->prev;
        curr->prev = curr->next;
        curr->next = temp;

        // Move curr to next node in original list (which is prev now)
        curr = curr->prev;
    }

    // After loop, temp points to previous node, update head
    if (temp != NULL) {
        *head_ref = temp->prev;
    }
}

// Print list from head to tail
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d", temp->data);
        if (temp->next != NULL) {
            printf(" ↔ ");
        }
        temp = temp->next;
    }
    printf(" -> null\n");
}

int main() {
    Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);

    printf("Original list:\n");
    printList(head);

    reverse(&head);

    printf("Reversed list:\n");
    printList(head);

    return 0;
}

while (curr != NULL) {

Traverse each node to reverse pointers

temp = curr->prev;

Store original prev pointer before swap

curr->prev = curr->next;

Swap prev and next pointers to reverse link

curr->next = temp;

Complete pointer swap for current node

curr = curr->prev;

Move to next node in original order (prev after swap)

if (temp != NULL) { *head_ref = temp->prev; }

Update head to new first node after reversal

Output

Original list:

1 ↔ 2 ↔ 3 -> null

Reversed list:

3 ↔ 2 ↔ 1 -> null

Complexity Analysis

Time: O(n) because we visit each of the n nodes once to swap pointers

Space: O(1) because we only use a few extra variables, no extra list

vs Alternative: Compared to creating a new reversed list (O(n) time and space), this reverses in place saving memory

Edge Cases

Empty list (head is NULL)

Function does nothing and head remains NULL

DSA C

while (curr != NULL) {

Single node list

Pointers swap but list remains same, head unchanged

DSA C

while (curr != NULL) {

When to Use This Pattern

When you see a problem asking to reverse a doubly linked list, reach for pointer swapping because each node has two links that must be flipped.

Common Mistakes

Mistake: Not updating the head pointer after reversal
Fix: Set head to the last processed node's prev pointer after loop ends

Mistake: Moving to curr->next instead of curr->prev after swapping
Fix: Move to curr->prev because pointers are swapped

Summary

Reverses the direction of a doubly linked list by swapping each node's prev and next pointers.

Use when you need to reverse the order of elements in a doubly linked list efficiently.

The key insight is that swapping prev and next pointers at each node reverses the entire list.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To convert it into a singly linked list

B. To delete all nodes from the list

C. To make the last node the first and the first node the last

D. To sort the list in ascending order

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes with pointers to both previous and next nodes.

2. Step 2: Define reversing operation

   Reversing means swapping the direction so the last node becomes the first and vice versa.

3. Final Answer:

   To make the last node the first and the first node the last -> Option C

4. Quick Check:

   Reverse = last becomes first [OK]

Hint: Reversing flips start and end nodes [OK]

Common Mistakes:

• Thinking reversing deletes nodes
• Confusing reversing with sorting
• Assuming it changes list type

2. Which of the following is the correct way to swap the next and prev pointers of a node in C?

easy

A. temp = node->prev; node->prev = node->next; node->next = node->next;

B. node->next = node->prev; node->prev = node->next;

C. node->prev = node->next; node->next = node->prev;

D. temp = node->next; node->next = node->prev; node->prev = temp;

Solution

1. Step 1: Use a temporary variable to hold one pointer

   Store node->next in temp to avoid losing its value.

2. Step 2: Swap pointers correctly

   Assign node->next to node->prev, then node->prev to temp.

3. Final Answer:

   temp = node->next; node->next = node->prev; node->prev = temp; -> Option D

4. Quick Check:

   Swap pointers using temp variable [OK]

Hint: Always use temp variable to swap pointers safely [OK]

Common Mistakes:

• Swapping without temp loses pointer data
• Assigning both pointers to same value
• Mixing order of assignments

3. Given the following doubly linked list nodes and code snippet, what will be the new head node's data after reversal?

struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

// List: 1 <-> 2 <-> 3 <-> NULL
struct Node* head = node1; // node1->data = 1

// Reversal code snippet:
struct Node* current = head;
struct Node* temp = NULL;
while (current != NULL) {
  temp = current->prev;
  current->prev = current->next;
  current->next = temp;
  current = current->prev;
}
if (temp != NULL) {
  head = temp->prev;
}

medium

A. 1

B. 3

C. 2

D. NULL

Solution

1. Step 1: Trace pointer swaps in the loop

   Each node swaps its next and prev pointers, moving current backward through original list.

2. Step 2: Update head after loop

   After loop, head is set to temp->prev, which points to original last node (data 3).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   New head = original tail = 3 [OK]

Hint: New head is original tail after reversal [OK]

Common Mistakes:

• Not updating head pointer after reversal
• Confusing prev and next pointers
• Assuming head remains same

4. Identify the error in the following code snippet that attempts to reverse a doubly linked list:

void reverse(struct Node** head_ref) {
  struct Node* current = *head_ref;
  struct Node* temp = NULL;
  while (current != NULL) {
    temp = current->next;
    current->next = current->prev;
    current->prev = temp;
    current = current->prev;
  }
  if (temp != NULL) {
    *head_ref = temp->prev;
  }
}

medium

A. temp should store current->prev instead of current->next

B. current should move to current->next instead of current->prev

C. The head pointer update is incorrect

D. No error, code is correct

Solution

1. Step 1: Verify pointer swaps

   The next/prev swaps correctly reverse directions as current traverses the original next chain (now in prev).

2. Step 2: Analyze temp assignment

   Temp should store current->prev before swapping, not current->next, to avoid losing pointer.

3. Final Answer:

   temp should store current->prev instead of current->next -> Option A

4. Quick Check:

   Correct temp assignment preserves traversal [OK]

Hint: Temp must hold current->prev before swapping pointers [OK]

Common Mistakes:

• Incorrect head pointer update logic
• Moving current incorrectly after swap
• Not updating head pointer properly

5. You have a doubly linked list with nodes containing integer data. After reversing the list using the standard pointer swap method, which of the following statements is TRUE about the list's traversal?

hard

A. Traversing from the new head using next pointers visits nodes in original reverse order

B. Traversing from the new head using prev pointers visits nodes in original order

C. Traversing from the original head using next pointers visits nodes in reversed order

D. Traversing from the new head using next pointers visits nodes in original order

Solution

1. Step 1: Understand reversal effect on pointers

   Reversing swaps next and prev pointers, so next pointers now point backward in original list.

2. Step 2: Analyze traversal from new head

   Starting at new head, following next pointers visits nodes in original reverse order.

3. Final Answer:

   Traversing from the new head using next pointers visits nodes in original reverse order -> Option A

4. Quick Check:

   Next pointers after reverse = original prev [OK]

Hint: Next pointers after reverse follow original prev links [OK]

Common Mistakes:

• Assuming next pointers still go forward after reverse
• Confusing traversal directions
• Thinking original head remains start