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

Example 2

Input: 10->4->3->2->1
Output: 1->2->3->4->10

Example 3

Input: 1->2->3
Output: 1->2->3