Given the head node of a singly linked list, sort the linked list in ascending order using the insertion sort algorithm. Return the head node of the sorted linked list. The insertion sort algorithm iterates through the list, inserting each node into its correct position in the sorted portion of the list.
Example 1
Input: ListNode(7, ListNode(3, ListNode(5, ListNode(2))))
Output: [2, 3, 5, 7]
Explanation: The sorted linked list is [2, 3, 5, 7].
Example 2
Input: ListNode(10, ListNode(-2, ListNode(8, ListNode(0))))
Output: [-2, 0, 8, 10]
Explanation: The sorted linked list is [-2, 0, 8, 10].
Constraints
Case 1
Input: ListNode(6, ListNode(1, ListNode(9, ListNode(4))))
Expected: [1, 4, 6, 9]
Case 2
Input: ListNode(0, ListNode(0, ListNode(0)))
Expected: [0, 0, 0]
Case 3
Input: ListNode(100)
Expected: [100]
Case 4
Input: ListNode(-3, ListNode(-1, ListNode(-2)))
Expected: [-3, -2, -1]