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:
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
And this is how the linked list is created before the reversal operation:
# Create the nodes first before linking them
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4
# Store references to Head node and Tail node
head = node1
tail = node4
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:
def reverse_iterative(head):
prev_node = None
current_node = head
# Traverse the list and reverse one link at a time
while current_node is not None:
# Store reference to next node
next_node = current_node.next
# Make link from current to prev node
current_node.next = prev_node
# Shift prev node reference to current node
prev_node = current_node
# Shift current node reference to next node
current_node = next_node
# prev_node contains the last node of linked list
# After reversal, it becomes the head node
# So return it as new head node of the reversed linked list
return prev_node
# Reverse the linked list using the iterative approach
head = reverse_iterative(head)
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.
def reverse_recursive(current):
if current is None or current.next is None:
return current
next_node = current.next
current.next = None # Break old link to prevent cycles
# Reverse links of all nodes from next_node
new_head = reverse_recursive(next_node)
# Reverse the link between current node and next_node
next_node.next = current
# Return the new head of the reversed list
return new_head
# Reverse the linked list using the recursive approach
head = reverse_recursive(head)
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.