# 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()
Now that we have the implementation of a Linked List in Python, we want to implement a method
reverse() which does the following:
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:
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()
View all Courses