![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007326243-Article_154.png\")
<\/p>\nx<\/p>\n
Linked list is one of the most famous and important data structures asked in most interviews. In this article, we will learn how to reverse a doubly linked list<\/p>\n
A doubly linked list is a data structure which contains nodes with points to the previous node as well to the next node.<\/p>\n
In this problem, we will be given a doubly linked list as input, and we need to reverse it such that the pointer currently pointing to the head of the list will point to the tail of the doubly linked list.<\/p>\n
According to the problem statement, we will be given a doubly-linked list, and we need to reverse a doubly linked list. <\/p>\n
Let’s understand this problem with the help of some examples.<\/p>\n
If the given doubly linked list is:<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/input-17.png\")
<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/output-16.png\")
<\/p>\n
Taking another example, if the given list is head -> 1 2 3 5 6 -> NULL.<\/p>\n
Some more examples<\/strong><\/p>\n Sample Input 1: 1 3 5 7 11 -> NULL. Sample Input 2: 2 3 5 7 11 17 -> NULL. Now, I think from the above examples, the problem statement is clear. Let\u2019s see how we can approach it.<\/p>\n Before moving to the approach section, try to think about how you can reverse a doubly linked list.<\/p>\n Let\u2019s move to the approach section.<\/p>\n This approach will be similar to reversing data present in an array. Time Complexity:<\/strong> O(n), 2 traversals will be required in this approach, one to get the address of the last node and another traversal to reverse the list.<\/p>\n Space Complexity:<\/strong> O(1)<\/p>\n The above approach will work fine, but the only issue is that we are traversing the doubly linked list twice. Now we need to ask ourselves one simple question: Do we actually need two list traversals to reverse the doubly linked list.<\/p>\n Is it possible to reverse a doubly linked list in a single traversal?<\/p>\n Let’s move to next approach.<\/p>\n Because we can access both the previous and next node of a given node in a doubly linked list, we can easily achieve list reversal by swapping the previous and next pointers of all nodes iteratively.<\/p>\n Let’s move to the algorithm section to see the above approach in depth.<\/p>\n
\nSample Output 1: 11 7 5 3 1 -> NULL.<\/p>\n
\nSample Output 2: 17 11 7 5 3 2 -> NULL.<\/p>\n\n
Approach 1 : Using 2 Pointers<\/h3>\n
\n1) We will initialize 2 pointers, one at starting and the other at the end of the linked list.
\n2) We will swap the node’s data to which the pointers are pointing.
\n3) And then, we will move the pointers toward’s each other by one step.
\n4) We will be performing step 2 and step 3 untill both the pointers do not cross each other or reach at the same position.
\n5) Finally, when both pointers reaches the same position, our doubly linked list will be fully reversed.<\/p>\n\n
Approach 2: Swapping<\/h3>\n
Algorithm<\/h3>\n
\n
Dry run<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-13.png\")
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-14.png\")
<\/p>\nCode Implementation to Reverse a Doubly Linked List:<\/h3>\n\t\t\t\t\t\t