Reversing Linked List | Data Structure

Reversing a linked list means changing the link part of all nodes of a linked list to pointing 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 is linked part to the node that comes right before every node. and in the end, we update the start variable’s position to the last node of the list. as you see in the image given below.

Method to reverse a linked list using 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 does become 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 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 will not reach the end of the list.

Now we 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