How to reverse a linked list in Python
Educative Answers TeamLinked 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
headstarts pointing to the last element of the list.
Given below is an iterative approach as to how you can reverse a given Linked List in Python:
- Initialize variables:
-
previous: Initially pointing atNone(line 3), this variable points to the previous element so thenode.nextlink 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 tohead(line 4), the node being pointed to by this variable gets itsnode.nextset to thepreviousitem 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 thecurrentpointer 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()RELATED TAGS
View all Courses
