You are given a singly linked list, write a program to sort it using insertion sort.

Problem Note:

  • Return the head of the sorted linked list
  • Try to solve the problem using in-place algorithm(O(1) space).

Example 1 

Input: 4->3->1
Output: 1->3->4
Explanation: Firstly, 1 is compared to all elements and put in place such that 1->4->3. Then 3 is put in place after comparing it to all elements such that 1->3->4. 4 is already in place and the list is sorted.

Example 2 

Input: 10->4->3->2->1
Output: 1->2->3->4->10
Explanation: 
1 is compared to give 1->10->4->3->2
2 is compared to give 1->2->10->4->3
3 is compared to give 1->2->3->10->4
4 is compared to give 1->2->3->4->10
10 is compared to give the sorted list 1->2->3->4->10.

Example 3 

Input: 1->2->3
Output: 1->2->3
Explanation: The list is already sorted.