We’re preparing your current view and syncing the latest data.
Given the head of a singly linked list, sort the list using insertion sort and return the sorted list's head.
Insertion sort iterates through the list, removing one node each iteration and inserting it into the correct position in a new sorted part of the list.
A singly linked list represented by its head node.
Return the head node of the sorted singly linked list.
The number of nodes in the list is in the range [1, 5000]. -5000 <= Node.val <= 5000
Example 1
Input
head = [4,2,1,3]
Output
[1,2,3,4]
Explanation
The input linked list is unsorted. After applying insertion sort, the linked list becomes sorted in ascending order.
Example 2
Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
Explanation
The input linked list contains negative and positive values. After sorting using insertion sort algorithm, the list is arranged in ascending order.