Reversing a Linked List

To reverse a linked list in Python with O(n) time complexity and O(1) space complexity, follow the following piece of code!

class Node:

	# The constructor used to initialize a Node 
	def __init__(self, data):
		self.data = data
		self.next = None


class LinkedList:

	# The constructor used to initialize the head to None 
	def __init__(self):
		self.head = None

	# The function to reverse 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

	# Helper function to push new data onto the linked list 
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# Helper function to print LinkedList 
	def printList(self):
		temp = self.head
		while(temp):
			print (temp.data)
			temp = temp.next

def main():
  # Driver code
  llist = LinkedList()
  llist.push(1)
  llist.push(2)
  llist.push(3)
  llist.push(4)
  
  print ("Given Linked List")
  llist.printList()
  llist.reverse()
  print ("\nReversed Linked List")
  llist.printList()


if __name__ == "__main__":
  main()

Output:

Check out our reel demonstrating the same at @detechtheory on Instagram!

Best,

Vasundhara