How to Reverse a Linked List in Python

Introduction

Reverse a linked list is one of the most important linked list operations that every CS student has to practice while learning data structure in school or college.

In this section, you'll learn how to reverse a linked list in python. We'll perform this task using two methods.

What can you learn from this section?

• How to create a linked list in python.

• How to reverse a linked list in python.

• Reverse a linked list using recursion.

Code

'''Reverse a linked list'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def addNode(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        temp = self.head
        while(temp.next):
            temp = temp.next
        temp.next = new_node

    def reverseList(self):
        prev = None
        current = self.head
        while(current):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

    def printNode(self):
        temp = self.head
        while(temp):
            print(temp.data, end='->')
            temp = temp.next
        print("\n")

if __name__ == "__main__":
    # Declaring a object of LinkedList class
    obj = LinkedList()
    obj.addNode(10)
    obj.addNode(20)
    obj.addNode(30)
    obj.addNode(40)
    obj.addNode(20)

    print("The Linked List is: ")
    obj.printNode()

    print("The Reverse Linked List is: ")
    obj.reverseList()
    obj.printNode()

Output

The Linked List is:
10->20->30->40->20->

The Reverse Linked List is:
20->40->30->20->10->

Reverse Linked List using Recursion

Now, we'll reverse a linked list using recursion.

Code

'''Reverse a linked list using recursion in python'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def addNode(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def reverseList(self, curr, prev):
        if curr.next is None:
            self.head = curr
            curr.next = prev
            return

        next = curr.next
        curr.next = prev

        # This function is calling itself
        self.reverseList(next, curr)

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

        self.reverseList(self.head, None)


    def printNode(self):
        temp = self.head
        while(temp):
            print(temp.data, end='->')
            temp = temp.next
        print("\n")


if __name__ == "__main__":
    # Declaring a object of LinkedList class
    obj = LinkedList()
    obj.addNode(1)
    obj.addNode(2)
    obj.addNode(3)
    obj.addNode(5)
    obj.addNode(6)

    print("The Linked List is:- ")
    obj.printNode()

    # Main function is calling the reverse function
    obj.reverse()

    print("The reverse linked list is:- ")
    obj.printNode()

Output

The Linked List is:-
6->5->3->2->1->

The reverse linked list is:-
1->2->3->5->6->