Question

First, create a project that creates an ordered linked list class (use the code provided, make sure to update the insert function so that it maintains an ordered list).

To this class, add a function that prints the list in REVERSE order. Making use of recursion is the easiest and best way to do this, but certainly not the only way.

Submit a .zip of your entire project.

Answer 1

The python code for the program for reversing an ordered linked list with predefined input is given below.

# Node class  
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 sortedInsert(self, new_node): 
          
        # Special case for the empty linked list  
        if self.head is None: 
            new_node.next = self.head 
            self.head = new_node 
  
        # Special case for head at end 
        elif self.head.data >= new_node.data: 
            new_node.next = self.head 
            self.head = new_node 
  
        else : 
  
            # Locate the node before the point of insertion 
            current = self.head 
            while(current.next is not None and
                 current.next.data < new_node.data): 
                current = current.next
              
            new_node.next = current.next
            current.next = new_node 




    # 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 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 
  
    # Utility function to print it the linked LinkedList 
    def printList(self): 
        temp = self.head 
        while(temp): 
            print(temp.data, end=" ")
            temp = temp.next
  
  
# Driver program 
l1 = LinkedList() 
new_node = Node(5) 
l1.sortedInsert(new_node) 
new_node = Node(10) 
l1.sortedInsert(new_node) 
new_node = Node(7) 
l1.sortedInsert(new_node) 
new_node = Node(3) 
l1.sortedInsert(new_node) 
new_node = Node(1) 
l1.sortedInsert(new_node) 
new_node = Node(9) 
l1.sortedInsert(new_node) 
print("\nInput Linked List ")
l1.printList()
l1.reverse() 
print("\nReversed Linked List ")
l1.printList()