# Reverse a linked list (iterative and recursive approaches)

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.

``````
# 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
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
# We want B.next to point to A
# Head node should point to it's previous node
``````

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:

``````
prev_node = None

# 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
``````

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:

1. Revese all the links from the next node
2. 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
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.