A linked list consists of nodes where each node contains an item/value along with a reference to next node in the sequence. Reversing a linked list involves changing the direction of the links for each node, effectively flipping the linked list from its original order to the opposite. This article will explore both iterative and recursive methods to reverse a linked list using Python.
For the code snippets in this article, linked list node is represented with the below structure:
And this is how the linked list is created before the reversal operation:
This is how the linked list looks like before reversal:
This is how the linked list should look like after reversal:
Base scenario
Before we discuss iterative and recursive approaches for reversing linked list, let’s go through a simple case of reversing a linked list with 2 nodes.
Let the linked list be A->B->None. Node A is the head node since it is at the start of list. After reversing, the list should be B->A->None. We can reverse the list by doing the following:
# head is Node A
# head.next is Node B
# We want B.next to point to A
head.next.next = head
# Head node should point to it's previous node
head.next = None
Now the list becomes B->A->None
We can rewrite the same logic in a more readable way:
current_node = head # The first node - Node A
prev_node = None # The node prev to first node - Nothing
next_node = head.next # The node next to first node - Node B
# Make link from current node to prev node
current_node.next = prev_node
# Make link from next node to current node
next_node.next = current_node
head = next_node # The last node will be the new head
Iterative Approach
The iterative method of reversing a linked list involves traversing the entire list while maintaining references to the previous, current, and next nodes. At each step in the traversal/iteration, link to the previous and current nodes is reversed by using logic similar to the base scenario discussed before. Below is the code:
Links are reversed one at a time at the statement current_node.next = prev_node. At the end of iteration, current_node points to the last node in the linked list and so it becomes the new head node of reversed linked list.
Recursive Approach
In order to understand the code recursive approach, we need to break down the original problem of reversing all the links in a linked list into two sub-problems:
- Revese all the links from the next node
- Reverse the link between current node and next node
The first sub-problem of reversing all links from the next node continues recursively until the end of list is reached. If you are new to recursion and confused how the code works, you may go through this introductory article on recursion before trying to understand the below code.
The return value of each recursive call is populated at the end of recursion, so it will be the last node of linked list. Since it should be the new head, the head is updated with the return value of reverse_recursive function.