Question

Implement a function that reverses a singly linked list in one pass of the list. The function accepts a pointer to the beginning of the list and returns a pointer to the beginning of the reversed list. The function must not create any new nodes. Be sure to test your function! You may start with code that you have written for other labs. This is a common interview question!

Answer 1

#save the following in filename.py

#creating a class for Node type
class Node:
#constructor to be called for Node class object
def __init__(self,data):
self.data=data
self.next=None
class SinglyLinkedList:
#constructor to be called for SinglyLinkedList object
def __init__(self):
self.head=Node(None)
#method to reverse linked list
def reverse(self):
previous_node=None
current_node=self.head
while(current_node is not None):
next_node=current_node.next
current_node.next=previous_node
previous_node=current_node
current_node=next_node
self.head=previous_node
#method to print SinglyLinkedList
def print(self):
curr=self.head
while(curr is not None):
print("{} ->".format(curr.data),end=" ")
curr=curr.next
print("NULL")
def add(self,data_in):
#creating a node with given data
node=Node(data_in)
#check if the head is null
if(self.head.data is None):
self.head=node
else:
current_node=self.head
#traverse through list and find last one
while(current_node.next is not None):
current_node=current_node.next
current_node.next=node
if __name__=="__main__":
#creating object for SinglyLinkedList class
SinglyLinkedListObj=SinglyLinkedList()
  
#adding elements to linked list
SinglyLinkedListObj.add(20)
SinglyLinkedListObj.add(10)
SinglyLinkedListObj.add(5)
  
print("\nPrinting list Before reversing ")
SinglyLinkedListObj.print()
  
#calling reverse method to reverse SinglyLinkedList in single pass
SinglyLinkedListObj.reverse()
  
print("\nPrinting list after reversing ")
SinglyLinkedListObj.print()