Untitled

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def insertion_sort(self):
        if (not self.head) or (not self.head.next):
            return
        else:
            sorted_head = None
            current_node = self.head

            while current_node:
                next_node = current_node.next
                sorted_head = self.insert_node(sorted_head, current_node)
                current_node = next_node

            self.head = sorted_head
            return

    def insert_node(self, temp_head, new_node):
        if (not temp_head) or temp_head.val >= new_node.val:
            new_node.next = temp_head
            temp_head = new_node

        else:
            current_node = temp_head

            while current_node.next and current_node.next.val < new_node.val:
                current_node = current_node.next

            new_node.next = current_node.next
            current_node.next = new_node

        return temp_head


def main():
    list1 = LinkedList()
    list1.head = ListNode(1)
    list1.head.next = ListNode(3)
    list1.head.next.next = ListNode(2)
    list1.head.next.next.next = ListNode(0)

    print_node = list1.head
    print(f"Input: {print_node.val}", end='')
    while print_node:
        if print_node.next:
            print(f" ->{print_node.next.val}", end='')
            print_node = print_node.next
        else:
            print("-›null")
            print_node = print_node.next

    list1. insertion_sort()

    print_node = list1.head
    print(f"Output: {print_node.val}", end='')
    while print_node:
        if print_node.next:
            print(f"-›{print_node.next.val}", end='')
            print_node = print_node.next
        else:
            print("->null")
            print_node = print_node.next


if __name__ == "__main__":
    main()