Reverse the Linked List in Python

In this tutorial, we will write the program of reverse the linked list in Python. The linked list is used to store the elements dynamically. The linked list is a linear data structure like the array, but it stores the element dynamically. Each element connects with its previous Node using the specific address and stores value along with the address of the next element. The whole element is known as the Node.

Here we will reverse the given linked using the Python program. Let’s understand the problem statement.

Problem Statement –

We need to provide the linked list and return its reverse as below.

  Input :  1-> 2-> 3-> 4-> NULL  Output : 4-> 3-> 2-> 1-> NULL    Input :  1-> 2-> 3-> 4-> 5-> NULL  Output : 5-> 4-> 3-> 2-> 1->NULL    Input : NULL  Output : NULL  

Let’s implement the solution of the given problem.

Method – 1

First, we will create the linked list and solve this problem using the iterative approach.

Code – Creating Linked List

  class Node:      def __init__(self, data):          self.data = data          self.next = None    class LinkedList:      def __init__(self):          self.head = None        def add_node(self, data):          newNode = Node(data)          if self.head != None:              current = self.head              while (current.next):                  current = current.next              current.next = newNode          else:              return None        def reverse_Llist(self):                  def print_list(self):          if self.head is not None:              current = self.head              while current:                  print(current.data, “->”, end = ”)                  current = current.next    n = LinkedList()  n.head = Node(1)  n1 = Node(2)  n.head.next = n1  n2 = Node(3)  n1.next = n2  n3 = Node(4)  n2.next = n3    n.print_list()  

Output:

1  -> 2  -> 3  -> 4  ->

In the above code, we have initialized the linked list and added some elements to it. Now, we will implement the iterative method of reversing the linked list.

Reverse the Linked List

We want to implement the reverse() method which does the following operations.

All the links start pointing in the opposite direction.
The head starts pointing to the last element of the list.

We will define the three pointers –

previous – It is an initial pointer which points None at starting, this pointer points to the previous element so the next link can be reversed using it.
current – It points initially head, the node being pointed to by this variable gets its node.next set to the previous item in the list.
after – It points the second node. We move this to one element head until it gets the next==None.

Let’s implement the reverse_Llist() function.

Example –

  def reverse_Llist(Llist):      if Llist.head == Node:          return None        previous = None      current = Llist.head      after = current.next         while current:          # Reverse the link          current.next = previous          # Moving previous element to one ahead          previous = current          # Moving current one element ahead          current = after          # Moving one element ahead          if after:              after = after.next        Llist.head = previous    n = LinkedList()  n.head = Node(1)  n1 = Node(2)  n.head.next = n1  n2 = Node(3)  n1.next = n2  n3 = Node(4)  n2.next = n3  print(“The reverse linked list is: “)  reverse_Llist(n)  n.print_list()  

Output:

The reverse linked list is:   4  -> 3  -> 2  -> 1  ->

Explanation –

In the above code, we have initialized the linked list instance and created the linked list. The reverse_Llist() function is called over the linked to reverse the list.

Method -2 – Recursive Method

  class Node:      def __init__(self, data):          self.data = data          self.next = None    class LinkedList:      def __init__(self):          self.head = None        def add_node(self, data):          newNode = Node(data)          if self.head != None:              current = self.head              while (current.next):                  current = current.next              current.next = newNode          else:              return None      def recusive_reverse(self, current, previous):                 # If last node mark it head          if current.next is None:              self.head = current                 # Update next to prev node              current.next = previous              return             # Save curr.next node for recursive call          after = current.next             # And update next          current.next = previous            self.recusive_reverse(after, current)        def reverse(self):          if self.head is None:              return          self.recusive_reverse(self.head, None)            def print_list(self):          if self.head is not None:              current = self.head              while current:                  print(current.data, ” -> “, end = ”)                  current = current.next  

Output:

The reverse linked list is:   4  -> 3  -> 2  -> 1  ->

Time Complexity: O(N)

Auxiliary Space: O(1)

Conclusion

In the above tutorial, we have implemented the solution to reverse the linked list problem. It is an essential concept of the linked list and can be asked in the interview question. We have solved this problem using Iterative and Recursive methods, and the time complexity will be the same in both methods.

Next TopicDifferences between Flatten() and Ravel() Numpy Functions

Reverse the Linked List in Python

Reverse the Linked List in Python

Problem Statement –

Method – 1

Reverse the Linked List

Method -2 – Recursive Method

Conclusion

Python Tkinter PanedWindow

T-Test in Python

You may also like