Reverse doubly linked list
In last two posts : Doubly linked list and Delete a node from doubly linked list, we learned how to insert and delete a node from a doubly linked list. In this post, we will discuss how to reverse doubly linked list. By reversing we mean next pointer should point to previous and previous pointer should point to next node. For example:
Original list : 2->7->6->12->10->1->NULL Reverse list : 1->10->12->6->7->2->NULL
While reversing singly linked list, two nodes were to be keep track, previous node and next nodes and only one pointer was to be change. Pointer pointing to next node was made to point to previous node.
Difference while reversing doubly linked list is that there are two pointers per node, previous and next. To put node in reverse doubly linked list, next pointer should be made to point to previous node where as previous pointer should be made to point to next node. That is the algorithm, follow it for all nodes.
Algorithm to reverse doubly linked list
1. Check if there is no node or only one node, return 2. While there is node in ddl, 2.a Save previous node of current node prev = current->prev 2.b Save next node of current node next = current->next 2.c Change current node's next to point to prev current->next = prev 2.d Change current node's prev to point to next current->prev = next 2.e move current to next node. current = next 3. Change headRef to point to last current node.
Reverse a doubly linked list implementation
Complexity of algorithm to reverse doubly linked list is O(n) as we have to traverse the entire list at least once.
Please share if there some other efficient or elegant method to so. Will sure put that on this blog. If you are interested in contributing to website or want to share interview experiences, please contact us.