Saturday, April 18, 2015

Reverse the doubly linked list

Problem

Reverse the doubly linked list

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/

Reactions:

0 comments:

Post a Comment