問題：Sort a linked list using insertion sort.
解題思路：插入排序的核心思想是，對一個已經(jīng)排好序的序列，現(xiàn)在有一個新的值馒吴，要把它插到合適的位置而使得序列前后的大小順序不變寺晌。這個問題的解決辦法很簡單，從前往后找第一個大于新值的數(shù)就可以了户魏，找到這個數(shù)后把這個數(shù)和它后面的數(shù)都往后挪一格驶臊，把新值插進(jìn)這個數(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;
}
}
