Reverse the doubly linked list

Problem

Input
10 - 8 - 4 - 2

Output
2 - 4 - 8 - 12

Solution

Method 1 - Reversing the prev and next references
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references 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).

void reverseDLL(Node head)  
 {  
    while(head!=null)  
    {  
       // 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  
    }  
 }

Time complexity - O(n)

Reference
http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/

Problem

Solution

See also