Given below is the implementation of a standard class-based singly Linked List in Python.
# A single node of a singly Linked Listclass Node:# constructordef __init__(self, data = None, next=None):self.data = dataself.next = next# A Linked List class with a single head nodeclass LinkedList:def __init__(self):self.head = None# insertion method for the linked listdef insert(self, data):newNode = Node(data)if(self.head):current = self.headwhile(current.next):current = current.nextcurrent.next = newNodeelse:self.head = newNode# print method for the linked listdef printLL(self):current = self.headwhile(current):print(current.data)current = current.next# Singly Linked List with insertion and print methodsLL = LinkedList()LL.insert(3)LL.insert(4)LL.insert(5)LL.printLL()
Now that we have the implementation of a Linked List in Python, we want to implement a method reverse()
which does the following:
head
starts 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:
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 variablesprevious = None # `previous` initially points to Nonecurrent = list.head # `current` points at the first elementfollowing = current.next # `following` points at the second element# go till the last element of the listwhile current:current.next = previous # reverse the linkprevious = current # move `previous` one step aheadcurrent = following # move `current` one step aheadif following: # if this was not the last elementfollowing = following.next # move `following` one step aheadlist.head = previous# TestingLL = 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()