JAva:チェーンテーブルのソート

タイトル説明: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) {


    }
}

【考え方】:挿入ソートを用いてソートを挿入する基本的な操作は、1つのデータを並べ替えられたソートデータに挿入し、新しい、個数に1を加えたソートデータを得ることであり、アルゴリズムは少量のデータのソートに適用され、時間複雑度はO(n^2)である.安定したソート方法です.挿入アルゴリズムは、ソートする配列を2つの部分に分けます.第1の部分には、この配列のすべての要素が含まれていますが、最後の要素を除いて(配列の複数の空間に挿入された位置があるようにします)、第2の部分には、この要素(すなわち、挿入される要素)しか含まれていません.最初の部分のソートが完了したら、最後の要素をソートされた最初の部分に挿入します.
ソートを挿入する基本的な考え方は、ステップごとにソートされるレコードをキー値の大きさで前にソートされたファイルの適切な位置に挿入し、すべて挿入が完了するまで挿入することです.

ListNode fakeNode=new ListNode(-1);  
        fakeNode.next=head;  
        if(head==null)  
            return null;  
        ListNode cur=head.next;//            
        ListNode pre=head;//            
        while(cur!=null)  
        {  
            if(cur.valval)  
            {  
                ListNode nextNode=cur.next;//              

                //           
                ListNode cur2=fakeNode.next;  
                ListNode temp=fakeNode;//  cur2        
                while(cur.val>cur2.val&&cur2!=pre)  
                {  
                    temp=cur2;  
                cur2=cur2.next;  
                }  
                //      
                temp.next=cur;  
                cur.next=cur2;  
                pre.next=nextNode;  
                //           
                cur=nextNode;  
            }  
            else {  
                pre=cur;  
                cur=cur.next;  
            }  

        }  

        return fakeNode.next;  

//コードは自己参照http://blog.csdn.net/u012249528/article/details/47151847