逻辑简单，代码难写，基础不劳，leecode写注释不能出现中文，太麻烦，我写了大量注释，链表问题最重要的就是你那个指针式干啥的
/**
* 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 list
cur.next=pre.next;
pre.next=cur;
cur=nextNode;
}
return h.next;
}
}
原文：/hansongjiang/p/3814998.html
