原题链接在这里：

题目：

Sort a linked list using insertion sort.

题解：

与类似. 

当出现cur.val > cur.next.val时就需要insert cur.next到对应位置.

Time Complexity: O(n^2). Space: O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode insertionSortList(ListNode head) {11         if(head == null || head.next == null){12             return head;13         }14         15         ListNode dummy = new ListNode(0);16         dummy.next = head;17         18         while(head.next != null){19             if(head.val > head.next.val){ //当出现前一个点val 比后一个点val大时，就要找到添加位置20                 ListNode mark = dummy;21                 while(mark.next != null && mark.next.val