In this article, you will learn how to read a linked list in reverse. Note that we only have to display values in the reverse direction. We do not need to reverse the actual linked list, meaning there is no need to update pointers, etc. Reading a linked list in the backward direction is easy. We can do so by using a recursive function. Given the head of the linked list, the steps to solve the given problem are given below.
read_in_reverse(head) If head is NULL return invoke read_in_reverse by passing head.next display the value of head
How to read a Linked List in a Reverse Order?
Consider the following figure for illustration.
In the above figure, you can see that we call the
read_in_reverse() function first with the head of the linked list, i.e., the node with the value 1. Then, the same function gets called recursively by passing
head.next as its argument. When the end of the list is reached, i.e., at step 5, we simply return.
After that, we display the value of the current node, i.e., the first value printed is 2, then 6, and so on. You can see that the last value read is 1 (at step 9), which is the value of the first node of the linked list.
The following code contains the implementation of the singly linked list to insert items and display them. It is followed by the
read_in_reverse() function that takes the head pointer and reads the linked list in the reverse direction.
#node for the linked list class Node: def __init__(self, value=None): self.value = value self.next = None #implementation of linked list class LinkedList: def __init__(self): self.head = None self.length = 0 #total number of elements in the linked list #adds a node at the end of the linked list def insert(self, value): node = Node(value) #create a node if self.head == None: #if list is empty insert a node at the start self.head = node else: temp = self.head #iterate through the list till last node is found while temp.next: temp = temp.next temp.next = node #adding a new node self.length += 1 #increment the length #traverse the complete list and print the node value def traverse(self): temp = self.head while temp: print(temp.value, end="\t") temp = temp.next print("") def read_in_reverse(head): if head== None: return read_in_reverse(head.next) print(head.value, end="\t") ll = LinkedList() #create linked list #insert values ll.insert(1) ll.insert(8) ll.insert(6) ll.insert(2) print("Given Linked list:") ll.traverse() print("Reading a Linked List in Reverse") read_in_reverse(ll.head)
Given Linked list: 1 8 6 2 Reading a Linked List in Reverse 2 6 8 1