public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);

        while(head != null){
            ListNode node = dummy;

            while(node.next != null && node.next.val < head.val){
                node = node.next;
            }

            ListNode tmp = head.next; //保存head的下一个节点
            head.next = node.next;  //拼接排序后半部分数组
            node.next = head;   //把前半部分排序数组和后半部分凭借
            head = tmp;  // 恢复head的下一个节点
        }

        return dummy.next;
    }
}