Python Program to Reverse a linked list

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list. We have to reverse the given list.

Problem Statement Understanding

Let’s try to understand this problem statement with help of examples.

Suppose the given linked list is:

Here we have to reverse this linked list. So to reverse the linked list, we will have to change the links of the all the nodes of the linked list such that:

• 1→7 will become 7→1.
• 7→15 becomes 15→7.
• 15→27 becomes 27→15.

27 will now become the new head of the linked list. So, the final reverse linked list will be

Input:

Output:

Explanation: The input list has been reversed.

This question is not a very complex one. We have to make use of list traversal in the question. The only change will be that we will be changing the links of each node.

Approach (Iterative)

The approach is going to be pretty simple:

• Create two nodes, say, prev and curr.
• prev will initially point to None and the curr will point to the head of the list.
• Now, we have to traverse through the list till the curr becomes None.
• For every node, we are going to store the next of curr in next and then will make the next of current point to prev. Finally we will make prev equal to curr, and curr equal to next.

By performing the above operations, we are changing the links of every node and ultimately reversing the list.

Algorithm

• Create two nodes – prev and current, prev will point to None and curr will point the head.
• Traverse through the list till curr becomes None.
• Store the next of curr in next.
• Now, make next of curr point to prev.
• After pointing to prev, we will make the prev equal to the curr, and curr equal to the next.
• In the end, after the full traversal, the prev will be our head (head = prev).

Dry Run

Code Implementation

class Node:

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


class LinkedList:

    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        current = self.head
        while(current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

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

    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data)
            temp = temp.next


llist = LinkedList()
llist.push(27)
llist.push(15)
llist.push(7)
llist.push(1)

print ("Given Linked List \n")
llist.printList()
llist.reverse()
print ("\nReversed Linked List")
llist.printList()

Output

Given Linked List
1 7 15 27
Reversed Linked List
27 15 7 1

Time Complexity – O(n), as list traversal is needed.
Space Complexity – O(1), as only temporary variables are being created.

Approach (Recursive)

The recursive approach is going to be very much similar to the iterative approach.

• If the current node is the last node, then we will mark it as our head, and it will now point to the prev node.
• If the base case fails, we will store the next of current in next, and make the current point to the previous node. After doing this, we will recur with next as current, and current as previous.

By performing the above operations, we are changing the links of every node and ultimately reversing the list.

Algorithm

• Base case – If the curr node is the last node, make it the head and also make next of curr point to the prev.
• Save the next of curr in next.
• Now, make the next of curr point to the prev.
• Recur with next as curr and curr as prev.

Finally, return the head.

Dry Run

Code Implementation

class Node:

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


class LinkedList:

    def __init__(self):
        self.head = None

    def reverseUtil(self, curr, prev):

        if curr.next is None:
            self.head = curr

            curr.next = prev
            return

        next = curr.next

        curr.next = prev

        self.reverseUtil(next, curr)

    def reverse(self):
        if self.head is None:
            return
        self.reverseUtil(self.head, None)



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

    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data),
            temp = temp.next

llist = LinkedList()

llist.push(27)
llist.push(15)
llist.push(7)
llist.push(1)

print ("Given linked list\n")
llist.printList()

llist.reverse()

print ("\nReverse linked list")
llist.printList()

Output

Given Linked List
1 7 15 27
Reversed Linked List
27 15 7 1

Time Complexity – O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to reverse a linked list in Python. Linked List reversal is an important concept when it comes to advanced concepts in the linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Other Python Programs
Python program to reverse a number
Python program for heap sort
Python program to check armstrong number
Python program to check leap year
Python program to convert celsius to fahrenheit
Python program to find factorial of a number
Python program to find the middle of a linked list using only one traversal
Python program to add two numbers