Insertion Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

• Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
• At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
• It repeats until no input elements remain.

Class Node:
    data (int)
    next (Node)

Example 1

Input:
    4 2 1 3
Output:
    1 2 3 4

Example 2

Input:
    -1 5 3 4 0
Output:
    -1 0 3 4 5

Constraints

• The number of nodes in the list is in the range [1, 10⁴]
• -5000 <= Node.data <= 5000
• Expected Time Complexity: O(n²)
• Expected Space Complexity: O(1)