Reversing Linked List Data Structure | DSA Tutorials

Reversing Linked List – Reversing a linked list means changing the link part of all nodes of a linked list to point to the nodes that come before every node.

As you see, we have a linked list that has four nodes, and to reverse this list, we need to point every node’s linked part to the node that comes right before it. And in the end, we update the start variable’s position to the last node of the list, as you see in Figure 2.

Reverse a linked list using the links of nodes

To reverse a linked list using the links of nodes, we need three references: prev, p, and next. In the beginning, we set the prev variable to None and set the reference of the first node of the linked list to variable p.

And then we start a loop till the value p becomes None. means till we don’t reach the last node of the list. In every iteration, we set the reference of the node that comes after node p into the variable next.

And then we set the linked part of node p equal to the prev variable.

After that, we store the reference of node p into the variable prev. So now the variable prev points to the node that points to variable p.

And then we change the reference of node p using the variable next, which means now the variable p points to the node that points to the variable next.

Now, these conditions will run until we reach the end of the list.

Now we have reached the end of the list because the linked part of node p is None. So now we update the self-variable value and point to the last node of the list.

So Now the linked list is reversed using the links of every node. 

Here is the Python code to reverse a linked list using the links of every node.

def reverse_list(self):
    prev = None    p = self.start
    while p is not None:
        next = p.link
        p.link = prev
        prev = p
        p = next
    self.start = prev

def reverse_list(self):
    prev = None    p = self.start
    while p is not None:
        next = p.link
        p.link = prev
        prev = p
        p = next
    self.start = prev