问题：Sort a linked list using insertion sort.
解题思路：插入排序的核心思想是，对一个已经排好序的序列，现在有一个新的值，要把它插到合适的位置而使得序列前后的大小顺序不变。这个问题的解决办法很简单，从前往后找第一个大于新值的数就可以了，找到这个数后把这个数和它后面的数都往后挪一格，把新值插进这个数原本的位置中。
那么对于一个还没有排好序的数组插入排序怎么弄？当然是从第一个数开始，把第二个数当成新值来处理，先把前两个数排序，然后第三个数当成那个新值来处理，然后前三个数就排好序了，又把第四个数当新值来处理，以此类推。
代码：
/**
* 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)||(head.next==null))
return head;
head=sort(head);
return head;
}
public ListNode sort(ListNode head)
{
ListNode now=head;
while(now!=null)
{
ListNode x=head;
while(x.val<now.val&&x!=now)
{
x=x.next;
}
ListNode start=x;
int last=x.val;
while(x!=now)
{
int temp=x.next.val;
x.next.val=last;
last=temp;
x=x.next;
}
start.val=last;
now=now.next;
}
return head;
}
}
