Leetcode Insertion Sort List

For insertion sort, the insertion is usually performed in a backward fashion:
start from the node just ahead, move left one by one, until find the correct insertion point (first left-node which is smaller than the insertee).

However, for single linked list, moving backwards is very hard since pointers to node's previous node is not available.  So each time we have to seek for insert-position from the list-head.

Then what? After find the insert-position, what should we do next?

Take the example of   0  3  4  5  1,  where 1 is the node to be inserted.
It is easy to identify that we need to insert in front of 3. In order to do this in place, I break this action into the following steps:

1. move the sub-sequence 3  4  5  to the right by one:  0  _  3  4  5 
2. insert 1 to the places which held 3 before: 0  1  3  4  5 

Talking about the implementation of the above, the choice can either be: just modify the values of related ListNode , or break the link and insert the nodes into the correct position.

I implemented via modifying values.