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.

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

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 –

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

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.