{"id":3434,"date":"2021-07-26T13:16:44","date_gmt":"2021-07-26T13:16:44","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3434"},"modified":"2022-02-25T06:28:29","modified_gmt":"2022-02-25T06:28:29","slug":"reverse-a-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/reverse-a-doubly-linked-list\/","title":{"rendered":"Reverse a Doubly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

Reverse a Doubly Linked List<\/h3>\n

In this problem, we will be given a doubly linked list as input and we need to reverse it.
\nLet the given input be:<\/p>\n

Input<\/strong>
\n\"\"<\/p>\n

Then the output will be:<\/p>\n

Output<\/strong>
\n\"\"<\/p>\n

Approach #1:<\/h3>\n

This approach is similar to reversing data in an array. We initialize 2 pointers one at starting and the other at end of the linked list and swap their data till both of them do not cross each other or become equal.<\/p>\n

NOTE :<\/strong> This approach may not be a good approach because a node might contain more than one data and then we would need to swap all of them hence approach #2<\/strong> is a more preferred approach.<\/p>\n

Time Complexity :<\/strong> O(n), but we need to loop the list twice. First, we will get the address of the last node then we will loop the list to reverse it.<\/p>\n

Space Complexity :<\/strong> O(1). <\/p>\n

Approach #2:<\/h3>\n

The method to reverse a doubly-linked list is very trivial. As we know that we could access the previous as well as the next node from a given node, we could easily achieve reversal of this list by swapping the previous as well as next pointers of all nodes iteratively.<\/p>\n

Code Implementation :<\/strong>
\n\t\t\t\t\t\t\t

Reverse a Doubly Linked List <\/h3>\r\n\t\t\t\t\t\t\t\t