Prerequisites

To learn how to reverse singly linked lists, you should know:

1. Python 3
2. Python data structures - List
3. In place list reversal
4. OOP concepts
5. Part 1  and Part 2 singly linked list

What will we learn?

In the last tutorials, we discussed what singly linked lists are, how to add a node, how to print all the nodes and how to remove a node. We strongly recommend you to read these first if you haven’t yet as we will be building off of those concepts.

This tutorial covers how to reverse a linked list. As discussed in the previous tutorial, you can perform an in place reversal by swapping the last and the first values and so on. But here we are going to discuss a different approach. The idea is to reverse the links. So 4-->2-->3 (head points to 4 , 3 points to None) will become 4<--2<--3 (head points to 3 , 4 points to None). This can be done iteratively and recursively.

We will keep track of three things: the current element, the previous element, and the next element. This is because once we reverse the link between the previous node and current node, we won’t be able to move to the next node of the current. That is why it becomes mandatory to track the next node of the current. Let us see this using an example:

Note: In the end, we point head pointer to the previous node.

How to implement this?

Now that you have a good handle on the linked list reversal, let's take a look at the related algorithm and code.

Iterative method

Algorithm

1. Set previous as None, current as head and next as the next node of current
2. Iterate through the linked list until current is None (this is the loop’s exit condition)
3. During each iteration, set the next node of current to previous
4. Then, set previous as current, current as next and next as its next node (this is the loop’s iteration process)
5. Once the current becomes None, set the head pointer to the previous node.

Code

def reverseList(list):

       #Initializing values
       prev = None
       curr = list.head
       nex = curr.getNextNode()
  
       #looping
       while curr:
           #reversing the link
           curr.setNextNode(prev)     

           #moving to next node      
           prev = curr
           curr = nex
           if nex:
               nex = nex.getNextNode()

       #initializing head
       list.head = prev

Recursive method

Algorithm

1. Pass the head pointer to this method as node.
2. Check if the next node of node is None:
   1. If yes, this indicates that we have reached the end of the linked list. Set the head  pointer to this node
   2. If no, pass the next node of node to the reverse method
3. Once the last node is reached, the reversing happens.

Code

def reverse(self,node):

       if node.getNextNode() == None:
           self.head = node
           return
       self.reverse(node.getNextNode())
       temp = node.getNextNode()
       temp.setNextNode(node)
       node.setNextNode(None)

Conclusion

Try to solve the above problem using in place reversal as well. The reversal serves as the base for solving other problems associated with linked lists which we will see in the future tutorials. Happy Pythoning!