問題：Sort a linked list using insertion sort.
解題思路：插入排序的核心思想是，對一個已經(jīng)排好序的序列，現(xiàn)在有一個新的值，要把它插到合適的位置而使得序列前后的大小順序不變。這個問題的解決辦法很簡單，從前往后找第一個大于新值的數(shù)就可以了，找到這個數(shù)后把這個數(shù)和它后面的數(shù)都往后挪一格，把新值插進這個數(shù)原本的位置中。
那么對于一個還沒有排好序的數(shù)組插入排序怎么弄？當(dāng)然是從第一個數(shù)開始，把第二個數(shù)當(dāng)成新值來處理，先把前兩個數(shù)排序，然后第三個數(shù)當(dāng)成那個新值來處理，然后前三個數(shù)就排好序了，又把第四個數(shù)當(dāng)新值來處理，以此類推。
代碼：

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