Jun 112012
 

Given a doubly linked list. Write a function that accepts a pointer to the head of the list and reverse 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:

I have earlier written post about reversing a singly linked list iteratively and recursively.

Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next pointers in all the nodes of the list and need to make head point to the last node of 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
———————————————————————-

  4 Responses to “Reversing a doubly linked list”

Comments (4)
  1. thank you it's easy way

  2. Its awesome! Thanks a lot

  3. thank you! it's great.

  4. thank you! it's great.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)