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"

node.py

class Node: """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

linkedlist.py

from node import Node class LinkedList: @staticmethod def sort(l): """Simple in-place sort of singly-linked list whose head is l""" # TODO Replace "pass" with your sort pass