Expected Behavior

Write a Python method sort() to sort a LinkedList object in descending order of the attribute _value. The code for the LinkedList class is shown below. You should use the sorting algorithm described here.

Given a LinkedList object llist, the execution of the code

llist.sort() print(llist)

should cause the sorted list to be printed out.

The code for the LinkedList class is as follows:

class Node: def __init__(self, value): self._value = value self._next = None # getter for the _value attribute def value(self): return self._value # getter for the _next attribute def next(self): return self._next def __str__(self): return str(self._value) + "; " class LinkedList: def __init__(self): self._head = None # add a node to the head of the list def add(self, node): node._next = self._head self._head = node # remove a node from the head of the list and return the node def remove(self): assert self._head != None _node = self._head self._head = _node._next _node._next = None return _node # insert node2 after node1 def insert(self, node1, node2): assert node1 != None node2._next = node1._next node1._next = node2 def __str__(self): string = 'List[ ' curr_node = self._head while curr_node != None: string += str(curr_node) curr_node = curr_node.next() string += ']' return string

Examples

Code:

ll = LinkedList() ll.add(Node(1)) ll.add(Node(3)) ll.add(Node(2)) ll.sort() print(ll)

Result: (this is the string returned by the __str__() method for the LinkedList class)

List[ 3; 2; 1; ]

Code:

ll = LinkedList() ll.sort() print(ll)

Result:

List[ ]

Code:

ll = LinkedList() ll = LinkedList() ll.add(Node(1)) ll.add(Node(1)) ll.add(Node(1)) ll.sort() print(ll)

Result:

List[ 1; 1; 1; ]