How To Reverse A Linked List, With Examples

There are many applications for linked lists, such as in music and image processing and representing graphs, trees, and more elaborate data structures. But why would you want to reverse a linked list? Let’s get into it.

What is a Reversed Linked List?

As you could probably guess, it’s a linked list that’s… been reversed! Normally, each node points to the next node in a list, starting from the head node and finishing at the tail node. But, when you reverse a linked list, the pointers are reversed, so that the head becomes the tail and the tail becomes the head. Consider the simple case of a 5-node list. This would normally look like this:

head → node1 → node2 → node3 → node4 → node5 → tail

once we reverse the list, we get:

tail → node5 → node4 → node3 → node2 → node1 → head

Even if the list becomes longer and involves more data values, the principle remains the same.

Why Would You Want to Reverse a Linked List?

Since a reversed linked list is still a linked list, in essence, a lot of the applications are similar. As such, reversed lists are still used in implementing further data structures, in stacks and in queues. But, there are some unique uses that reverse linked lists bring to the table:

• Since the elements are reversed, we can print the elements and process the list in reverse order. This is helpful if you want to display a browser’s internet history.
• If you want to delete some elements near the end of the list, reversing it makes this a lot easier. This is because these elements are now at the beginning of the list. This can save a lot of time, especially if the list is substantial in size. You don’t need to traverse the whole list if you reverse the list.
• Sometimes, we want to perform a recursive algorithm on an entire list, executing operations at each node. In some of these cases, processing them in reverse order may make more sense.
• Another reason to use a reversed linked list is to check if the list is palindromic – this means that the sequence is the same forwards or backwards. An example of this would be the number 212. Whichever way you look at it, the sequence of data values is identical.

How to Reverse a Linked List

There are generally two approaches to reversing a linked list – the iterative approach and the recursive approach. Let’s take a look at these.

The Iterative Approach

In this method, we repeat the execution of the algorithm until each pointer has been reversed. We do this by tracking our nodes using “prev”, “curr” and “next” attributes. We can assign these as such:

while (current != NULL)
{
next = current -> next
current -> next = prev
prev = current
current = next 
}
head_ref = prev

The “while” statement basically iterates over each node that isn’t null.

The next line keeps track of the next node in the list, so we don’t lose it once we reverse the pointers.

Then, we set the “next” attribute of the current node to the previous node, reversing the pointers.

The next line sets the “prev” attribute to the previous node, keeping track of it like we did the next node.

The penultimate line says that the “current” pointer is on the next node, so we can move iteratively along the list.

Lastly, we set the “head_ref” pointer to the last node of the original list, which will be the first node in the reversed list. Therefore, we set this as the new head node.

Here’s how we can implement this process in Python:

class Node:
   def __init__(self, data):
     self.data = data
     self.next = None

class LinkedList:
    def __init__(self):
     self.head = None

    def push(self, new_data):
      new_node = Node(new_data)
      new_node.next = self.head
      self.head = new_node

    def reverse(self):
      prev_node = None
      current_node = self.head
      while current_node is not None:
          next_node = current_node.next
          current_node.next = prev_node
          prev_node = current_node
          current_node = next_node
      self.head = prev_node

    def printList(self):
       current_node = self.head
       while current_node:
          print(current_node.data, end=" ")
          current_node = current_node.next

my_list = LinkedList()
my_list.push(16)
my_list.push(2)
my_list.push(19)
my_list.push(71)

print("Given linked list")
my_list.printList()
my_list.reverse()
print("\nReversed linked list")
my_list.printList()

First, we define the classes “Node” and “LinkedList”. Then, we define the “push” function, which is used to add a new node to the beginning of the list, which is designated as the head node.

Then, we see the “reverse” function implemented in very much the same way as previously described.

Finally, we’re defining the “printList” function for the “LinkedList” class, which prints the data value at each node, which continues until the “current_node” is equal to “None”, indicating that we’ve reached the end of the list. See the screenshot for how this works in Python.

The Recursive Approach

The other method for reversing a linked list is the recursive approach. Whereas iterative approaches work by using loops or repetitive instructions to solve a problem, recursive approaches execute the same function on smaller and smaller examples of the same problem. Once these subproblems are solved, the solutions are combined to give an overall result to the initial problem. Let’s see how recursion works for reversing a linked list:

First, we divide the list into two parts, the first node, and the remaining list.

Then, we call the “reverse” function for the remaining list.

This reversed list is then linked to the first node, and the original head pointer is set to NULL. The new head pointer is set to the new head node, and the list is reversed.

Here’s a look at how this is implemented:

class Node:
   def__init__(self, data):
     self.data = data
     self.next = None

class LinkedList:
   def__init__(self):
     self.head = None

   def push(self, new_data):
     new_node = Node(new_data)
     new_node.next = self.head
     self.head = new_node

   def reverse_recursive(self, current_node):
     if current_node is None or current_node.next is None:
        return current_node

     rest = self.reverse_recursive(current_node.next)

     current_node.next.next = current_node
     current_node.next = None

     return rest

   def reverse(self):
     self.head = self.reverse_recursive(self.head)

   def printList(self):
     current_node = self.head
     while current_node:
       print(current_node.data, end =" ")
       current_node = current_node.next
     print()

my_list = LinkedList()
my_list.push(16)
my_list.push(2)
my_list.push(19)
my_list.push(71)

print("Given linked list")
my_list.printList()

my_list.reverse()
print("Reversed linked list (recursive):")
my_list.printList()

A lot of this code is the same as the iterative process. The main difference is, unsurprisingly, in the reverse function used.

In this case, we define the function “reverse_recursive” as a function of the current node. Each node after this is recursively reversed by calling the reverse function with the next node as input until the current node is equal to “None”. This happens when the end of the list is reached, or in the simple case where there’s only one node in the list.

Then, the current node is reversed by updating the “next” attribute of the next node to the current node, and the “next” attribute of the current node to “None”. The current node becomes the tail of the reversed list.

Wrapping Up

When you need to reverse a linked list, you can choose between an iterative approach and a recursive approach. Whereas iterative approaches rely on repeating the same instructions in a “while” loop for each node, recursive functions execute their function on smaller instances of the same problem. Reversing a linked list can be useful to detect the palindromicity of a list and modify elements at the end of the original list.