Question

Python 3 Function which takes the head Node of a linked list and sorts the list into non-descending order. PARAM: head_node The head of the linked list RETURNS: The node at the head of the sorted linked list. '''

def sort(head_node):

#Code goes here

''' Test code goes here ''

' if __name__ == '__main__':

Answer 1

'''

Python version : 3.6

Python program to sort a linked list

'''

# class representing the node of the linked list

class Node:

               # initializes a node

               def __init__(self, value):

                              self.value = value

                              self.next = None

              

               # function to set the value of the node    

               def setValue(self,value):

                              self.value = value

              

               # function to set the next pointer of the node       

               def setNext(self,next):

                              self.next = next

              

               # function to return the value of the node

               def getValue(self):

                              return self.value

              

               # function to return the pointer of next node

               def getNext(self):

                              return self.next

              

               # function to return the string representation of the node

               def __str__(self):

                              return('%s' %(str(self.value)))

                             

# function to sort a linked list that starts with the head_node                        

def sort(head_node):

              

               swapped = True

               # loop that continues till the list is sorted

               while swapped:

                              swapped = False

                             

                              curr = head_node

                              # loop that continues till the end of the list

                              while curr.getNext() != None:

                                             # if value at curr node is greater than value at node next to curr then swap the values

                                             if curr.getValue() > curr.getNext().getValue():

                                                            temp = curr.getValue()

                                                            curr.setValue(curr.getNext().getValue())

                                                            curr.getNext().setValue(temp)

                                                            swapped = True # set swapped to True

                                             curr = curr.getNext()

               return head_node # return the head_node of the sorted linked list

# function to insert the value at the end of the linked list  

def insert(head_node, value):

               node = Node(value)

               if head_node == None:

                              head_node = node

               else:

                              temp = head_node

                              while temp.getNext() != None:

                                             temp= temp.getNext()

                                                           

                              temp.setNext(node)       

               return head_node

# function to display the linked list            

def display(head_node):

               node = head_node

                             

               if node == None:

                              print('Empty list')

               else:

                              while(node != None):

                                             print(str(node),end=' ')

                                             node = node.getNext()

                              print('')                

# Test the functions                       

if __name__ == "__main__":

              

               head_node = None

              

               head_node = insert(head_node,23)

               head_node = insert(head_node,12)

               head_node = insert(head_node,20)

               head_node = insert(head_node,15)

               head_node = insert(head_node,19)

              

               display(head_node)

               head_node = sort(head_node)

               display(head_node)

              

#end of program             

Code Screenshot:

Output: