[leetcode]insertion-sort-list

问题：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;
    }
}