Reversing a Doubly Linked List

Given a doubly linked list. Write a function that accepts a pointer to the head of the list and reverses the list.

The structure of the node in a doubly linked list is as below:
struct Node
{
   int data;
   Node* prev; // pointer to the previous node in the list
   Node* next; // pointer to the next node in the list
};

Solution:

Reversing a doubly linked list is much simpler than reversing a singly linked list. We just need to swap the prev and next pointers in all the nodes of the list and make the head point to the last node of the original list (which will be the first node in the reversed list).

Here is the code


void reverseDLL(Node*& head)
 {
    while(head)
    {
       // Swapping the prev & next pointer of each node
       Node * t = head->prev;
       head->prev = head->next;
       head->next = t;
       if(head->prev != NULL)
          head = head->prev;  // Move to the next node in original list
       else
          break;              // reached the end. so terminate
    }
 }
 

Please let me know your comments / feedback / suggestions 

0 Comments

Leave a comment