/** * 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;            }               }