How to reverse a linked list in Python

Linked List in Python

Given below is the implementation of a standard class-based singly Linked List in Python.

# A single node of a singly Linked List
class Node:
# constructor
def __init__(self, data = None, next=None):
self.data = data
self.next = next
# A Linked List class with a single head node
class LinkedList:
def __init__(self):
self.head = None
# insertion method for the linked list
def insert(self, data):
newNode = Node(data)
if(self.head):
current = self.head
while(current.next):
current = current.next
current.next = newNode
else:
self.head = newNode
# print method for the linked list
def printLL(self):
current = self.head
while(current):
print(current.data)
current = current.next
# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert(3)
LL.insert(4)
LL.insert(5)
LL.printLL()

Reversing a linked list

Now that we have the implementation of a Linked List in Python, we want to implement a method reverse() which does the following:

  • All the links start pointing in the opposite direction.
  • The head starts pointing to the last element of the list.
Reversing a Linked List
Reversing a Linked List

Given below is an iterative approach as to how you can reverse a given Linked List in Python:

  • Initialize variables:
    • previous: Initially pointing at None (line 3), this variable points to the previous element so the node.next link can be reversed using it (line 9). This is then updated to the node next to it, i.e., current (line 10).

    • current: Initially pointing to head (line 4), the node being pointed to by this variable gets its node.next set to the previous item in the list (line 9). This is then updated to the node next to it,​ i.e., following (line 11).

    • following: Initially pointing to the second node (line 5), this is used so the current pointer may move one step ahead (line 12-13) in each iteration.

def reverseList(list):
# initialize variables
previous = None # `previous` initially points to None
current = list.head # `current` points at the first element
following = current.next # `following` points at the second element
# go till the last element of the list
while current:
current.next = previous # reverse the link
previous = current # move `previous` one step ahead
current = following # move `current` one step ahead
if following: # if this was not the last element
following = following.next # move `following` one step ahead
list.head = previous
# Testing
LL = LinkedList()
LL.insert(1)
LL.insert(2)
LL.insert(3)
LL.insert(4)
print("Linked List")
LL.printLL()
print("Reversed Linked List")
reverseList(LL)
LL.printLL()
Copyright ©2024 Educative, Inc. All rights reserved