Question

I've provided a Node class that implements a node of a simple singly-linked list (with .value and .next fields), and an empty LinkedList class. Your task is to implement LinkedList.sort(l), where given the node l as the head of a singly-linked list, LinkedList.sort(l) sorts the nodes in the list into ascending order according to the values in the .value field of each node.

Your implementation should do an in-place update of the list. It is ok to use a simple O(n**2) algorithm.

Examples

1. 'b'->'a'->'d'->'c' sorts to 'a'->'b'->'c'->'d'

2. 3->2->1 sorts to 1->2->3

3. "this"->"that" sorts to "that"->"this

this is the provided code you have to fill it in here:

class ListNode:
    """Simple node for singly-linked list"""

    def __init__(self, value, next=None):
        """Create a new node, with optional next node pointer"""
        self.value = value
        self.next = next

def listsort(l):
        """Simple in-place sort of singly-linked list whose head is l"""
        # TODO Replace "pass" with your sort

IN PYTHON PLEASE!!!

Answer 1

Given below is the code for the question. PLEASE MAKE SURE INDENTATION IS EXACTLY AS SHOWN IN IMAGE.
Please do rate the answer if it helped. Thank you.

class ListNode:
   """Simple node for singly-linked list"""

   def __init__(self, value, next=None):
       """Create a new node, with optional next node pointer"""
       self.value = value
       self.next = next

def listsort(l):
       """Simple in-place sort of singly-linked list whose head is l"""
       # use version of selection sort
       p = l
       while p != None:
           minNode = p
           q = p.next
           while q != None:
               if q.value < minNode.value:
                   minNode = q
               q = q.next
          
           #swap the values in minNode and p
           temp = p.value
           p.value = minNode.value
           minNode.value = temp
          
           p = p.next