Related Blog Items

• Reversing a circular single linked list using pointers
• Reversing a single linked list using stack
• Reversing single linked list recursively
• Detecting broken links in double linked list
• Circular Doubly Linked List With Out Using Special Head or Tail Node

refer double linked list post for information about double linked list. Here in this post we will be discussing about reversing a double linked list.

Here is the pictorial representation of our algo…

in our routine we will swap our next, prev pointers of nodes to reverse the double linked list… this routine capable of reversing entire list for given any node in the double linked list.

The below routine takes input as any node in double linked list and reverse the entire double linked list and returns same node pointer.

Node *reverselist(Node *head)
{
  Node* n = head;
  Node *tmp, *tmp2;
  Node* after = head->next;
  Node* before = head->prev;
 
  //reverse all nodes after n (if any)
 
  //now reverse nodes after head
  while(n && after)
  {
    tmp = after->next;
    tmp2 = after;
 
    after->next = n;
    n->prev = after;
 
    after = tmp;
    n = tmp2;
  }
  //make the last node prev ptr points to NULL
  n->prev = NULL;
 
  //search all nodes before n (if any)
  n = head;
 
  //now reverse all nodes before head
  while(before && n)
  {
    tmp = before->prev;
    tmp2 = before;
 
    before->prev = n;
    n->next = before;
 
    before = tmp;
    n = tmp2;
  }
  //make the first node next ptr points to NULL
  n->next = NULL;
 
  return head;
}

any comments welcome…

Popularity: 51%

You need to log on to convert this article into PDF

Related Blog Items

• Reversing a circular single linked list using pointers
• Reversing a single linked list using stack
• Reversing single linked list recursively
• Detecting broken links in double linked list
• Circular Doubly Linked List With Out Using Special Head or Tail Node

This entry was written by ponnada and posted on March 30, 2007 at 5:43 pm and filed under Algorithms, C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.