To learn how to reverse singly linked lists, you should know:
- Python 3
- Python data structures - List
- In place list reversal
- OOP concepts
- 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:
|Linked list||prev||curr||nex||After reversal|
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.
- Set previous as None, current as head and next as the next node of current
- Iterate through the linked list until current is None (this is the loop’s exit condition)
- During each iteration, set the next node of current to previous
- Then, set previous as current, current as next and next as its next node (this is the loop’s iteration process)
- Once the current becomes None, set the head pointer to the previous node.
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
- Pass the head pointer to this method as node.
- Check if the next node of node is None:
- If yes, this indicates that we have reached the end of the linked list. Set the head pointer to this node
- If no, pass the next node of node to the reverse method
- Once the last node is reached, the reversing happens.
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)
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!