逻辑简单，代码难写，基础不劳，leecode写注释不能出现中文，太麻烦，我写了大量注释，链表问题最重要的就是你那个指针式干啥的
提交地址/problems/insertion-sort-list/
/*** Definition for singly-linked list.* public class ListNode {*int val;*ListNode next;*ListNode(int x) {* val = x;* next = null;*}* }*/public class Solution {public ListNode insertionSortList(ListNode head) {if(head==null) return head;ListNode h=new ListNode(-1000000); //加入头结点方面，特别适合头结点不断改变的情况，c++要释放掉，java直接返回头的next就可h.next=head;ListNode cur=head.next; //cur 保存当前处理的节点head.next=null; //别忘了，新链表的尾巴值为空while(cur!=null){ListNode nextNode=cur.next; //保存下一个要处理的点，因为cur会被插入的新链表中，所以保存，然后赋给cur（最后一句）ListNode l=h.next;ListNode pre=h;while(l!=null) //找到合适的插入位置，找pre地址{if(l.val<=cur.val){pre=l;l=l.next;}else{break;}}//insert into the listcur.next=pre.next;pre.next=cur;cur=nextNode;}return h.next;}}
