Reverse a Linked List using Python

0
2 min read

This blog post will help your to learn, How to reverse Linked List using Python.

Input: Before reverse operation on Linked List 
1->2->3->4->NULL 
Output: After Reverse operation Linked list will look like, 
4->3->2->1->NULL

So to reverse a Linked List, we have to create a three points

  • Prev
  • Current
  • next
Source: Learnersbucket.com

How to create Node in SIngly Linked List using python, You can read out here in few words https://freshlybuilt.com/question/how-to-create-node-for-linked-list-using-python/

Algorithm for Reverse a Linked List

  • Initialize three pointers prev as None, curr as head and next as None
  • Iterate through the linked list.
  • In a Loop follow the bellow steps.
  • Before changing the next of current store next node i.e next = current.next
  • Now change the next of current, This is a point where actual reversing happens i.e current.next = prev
  • Move the prev and current one step forward i.e prev = current, current = next

Reverse a Linked List – Python Code

# Structure for node
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 reverse(self): 
		prev = None
		current = self.head 
		while(current is not None): 
			next = current.next
			current.next = prev 
			prev = current 
			current = next
		self.head = prev 
		
	# Function to insert a new node at the beginning
        # Function to push data 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 linked LinkedList 
	def printList(self): 
		temp = self.head 
		while(temp): 
			print(temp.data) 
			temp = temp.next


linked_list = LinkedList() 
linked_list.push(1) 
linked_list.push(2) 
linked_list.push(3) 
linked_list.push(4) 

print("Given Linked List will look like ")
linked_list.printList() 
linked_list.reverse() 
print("After reverse function, Reversed Linked List will look like")
linked_list.printList() 

Output

Given Linked List will look like
1 2 3 4
After reverse function, Reversed Linked List will look like
4 3 2 1
  • Time Complexity: O(n)
  • Space Complexity: O(1)

It is one of the simplest method to reverse a linked list. What are your views about the recursive method for reversing a linked list. Do you think it is better than this one, Comment it out in comment section. Let’s have good discussion.

Choose your Reaction!
Leave a Comment