Reverse linked list Python
In this post, you will learn how to implement a reverse linked list using the Python programming language.
The linked list is a non-primitive data structure which is free from fixed memory size restrictions. It is a linear collection of data elements and dynamic in nature. A linked list element cannot be stored in a consecutive memory. It is static-free and the user can add any number of elements when required. The linked list is a data structure and is used to create other data structures, like stacks, queues, etc. It allows the insertion and deletion of nodes at any point in the list.
Python Program to Reverse a linked list using Iterative Method
In the given Python program, we have initialized the linked list and added some elements to it using the push() method. Next, we implement the iterative method (while loop) for reversing the linked list.
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to reverse the linked list
def reverseList(self):
prev = None
curr = self.head
while(curr is not None):
next = curr.next
curr.next = prev
prev = curr
curr = next
self.head = prev
# Function to insert a new node at the beginning
def push(self, ele):
new_node = Node(ele)
new_node.next = self.head
self.head = new_node
# Function to print the LinkedList
def displayList(self):
temp = self.head
while(temp):
print (temp.data,end=" ")
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(12)
llist.push(27)
llist.push(65)
llist.push(45)
llist.push(22)
print("Original Linked List : ")
llist.displayList()
llist.reverseList()
print("\nReversed Linked List : ")
llist.displayList()
Output of the above code:
Original Linked List :
22 45 65 27 12
Reversed Linked List :
12 27 65 45 22
Python Program to Reverse a linked list using Recursive Method
A recursion function is a function that is called by itself. In the given Python program, we use the recursion function to get the reverse linked list. First, we initialised the linked list instance and created the linked list. The reverseList() function is called over the linked to reverse the list.
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
def reverseList(self, curr, prev):
# If last node mark it head
if curr.next is None:
self.head = curr
# Update next to prev node
curr.next = prev
return
next = curr.next
curr.next = prev
self.reverseList(next, curr)
def reverse(self):
if self.head is None:
return
self.reverseList(self.head, None)
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to print the LinkedList
def printList(self):
temp = self.head
while(temp):
print(temp.data,end=" ")
temp = temp.next
# Driver program
list1 = LinkedList()
list1.push(23)
list1.push(63)
list1.push(27)
list1.push(19)
list1.push(42)
list1.push(28)
print("Original linked list: ")
list1.printList()
list1.reverse()
print("\nReverse linked list: ")
list1.printList()
Output of the above code:
Original linked list:
28 42 19 27 63 23
Reverse linked list:
23 63 27 19 42 28
Related Articles
Count consonants in a string Python
Python split strings by comma
Count vowels in a string Python
Replace multiple characters Python
Convert array to list Python
Python loop through list
Difference between tuple and list in Python
Convert string to list Python
Remove last element from list Python
Convert list to string Python
Convert Python list to numpy array
Remove element from list Python
Python dict inside list
Check if list is empty Python
Python iterate list with index
Python iterate list with index
Python split string by comma
Printing Simple Diamond Pattern in Python
Stemming and Lemmatization in Python
Python | Generate QR Code using pyqrcode module