Reversing a Doubly Linked List Data Structure | DSA Tutorials

Reversing a Doubly Linked List – To reverse a doubly linked list, we have two approaches: either reverse the links of every node or reverse the values of nodes.

Reverse a Doubly Linked List – Method

In this tutorial, we are going to reverse a doubly-linked list by reversing its links. like if we have a doubly-linked list that has four nodes, as you see in Figure 1.

After reversing this linked list, the start variable refers to the last node of the list, and the first node becomes the last node, and the last node becomes the first node. So our new reversed linked list should be like this, as you see in Figure 2.

So, to reverse a linked list, first we need two references, p1 and p2. Initially, we set p1 to point to the first node of the linked list and p2 to point to the second node of the linked list.

After that, we store the p1 node’s previous link part in the p1 node’s next link part, as you see in Figure 2.

And then we store the p2 node’s reference in the p1 node’s previous link part.

After that, we start a loop that will be run till the value of variable p2 becomes None or Null. It means the loop will run until we reach the last node of the linked list. In every iteration, first, we store the p2 node’s next link part’s value in the p2 node’s previous link part.

Second, we store the p1 node’s reference in p2 node’s next link part.

Third, we set p1 to the next node that comes after node p1 using the p2 node.

Fourth we set p2 to the next node that comes after node p2 using the previous link part of node p2.

So in every iteration, these four conditions will apply, and this condition will run till we don’t reach the last node of the linked list or till the value of the node, p2 becomes None or Null.

So now the value of variable p2 becomes None, which means we reached the last node of the linked list so we store the p1 node’s reference into the start variable, because the start variable always refers to the first node of the linked list.