Prerequisites
How to reverse a singly linked list: 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?
Reverse singly linked list: 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 |
(h)4–>2–>3(None) | None | 4 | 2 | (None)4–>2–>3 |
(None)4–>2–>3 | 4 | 2 | 3 | (None)4<–2–>3 |
(None)4<–2–>3 | 2 | 3 | None | (None)4<–2<–3 |
(None)4<–2<–3 | 3 | None | None | (None)4<–2<–3(h) |
- Singly Linked List: How To Find and Remove a Node
- Java Program to Create a Singly Linked List, Add Elements to it and Display
- Java Program to Remove Duplicate Elements from a Singly Linked List
Note: In the end, we point head pointer to the previous node.
How to implement this?
Reverse a singly linked list java: 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
- 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.
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
- 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.
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!