Reverse Linked List

In this lesson, we will learn how to reverse a linked list using recursion.

We'll cover the following

What is a Linked List?

A linked list is a data structure that stores data in the form of a sequence of nodes. Each Node holds data along with a forward pointer to the next Node in the list.

As you can see in the illustration below, a linked list is formed by Nodes which are linked together like a chain.

Illustration of a linked list
Illustration of a linked list

If you want to learn more about linked list have a look at our Interview Refresher course on Data Structures in Python.

What does “Reversing a Linked List” Mean?

A linked list contains a sequence of data. Our task is to reverse that sequence:

Reversing a linked list
Reversing a linked list

Implementation

Press + to interact
main.py
linkedList.py
node.py
import node as n
class LinkedList: 
	def __init__(self) :
		self.head = None
	def append(self, new_data): 
		new_node = n.Node(new_data) 
		
		if self.head is None : # If head node is null 
			self.head = new_node 
			return
		last = self.head 
		while (last.next): 
			last = last.next
		last.next =  new_node # add new node to end of list
	def printList(self):
		temp = self.head
		while(temp):
			print(temp.data)
			temp = temp.next

Explanation

In the code snippet above, we pass our linked list myLinkedList to the function reverse(). This function checks whether the head of the linked list is null or not. If it exists, we call the helperFunction(). This function is recursive and is actually where reversal of the linked list takes place.

In helperFunction(), the nodes are reversed using the following statements:

next = current.next # The original next node of the current node is saved
current.next = previous # The next of the current node is updated

After this change, we recursively call the function again:

# Recursive case
helperFunction(myLinkedList, next, current)

# The current node in the next recursive call will be the "next" node that we saved.
# The previous node will be the parent function's current node

The base case for this problem will be when we reach the end of the linked list, in which case the next node of the current node will be None. We will make this last node the head of the linked list, update its position and return.

To better understand this algorithm have a look at the sequence of function calls:

In the next lesson, we will learn how to perform depth first traversal using recursion in graphs.