LintCodeチェーンテーブル挿入ソート
1.説明
挿入ソートによるチェーンテーブルのソート
サンプル
Given
2.分析
挿入ソートは、配列の挿入ソートと同様に、チェーンテーブルの挿入ソートに関する一般的なソート方法の1つです.
原題はheadをヘッダノードとするチェーンテーブルを与え、次に秩序あるdummyチェーンテーブルを新規作成し、headチェーンテーブルを
のノードをdummyチェーンテーブルにそれぞれ挿入してheadチェーンテーブルのソートを完了します.順序付きチェーンテーブルで順次下に検索することを想定
元のチェーンテーブルの値と比較して、秩序チェーンテーブルの値が元のチェーンテーブルの値より大きい場合、その値を秩序チェーンテーブルに挿入します.例を挙げると
秩序チェーンテーブルには1、3があり、元のチェーンテーブルには2があります.1と2は先に比較して、1は2より小さくて、引き続き下へ探して、3は2より大きくて、この時元のチェーンテーブルを
の2を1、3の間に挿入して、最終的に秩序チェーンテーブル1、2、3を得る.
シーケンスチェーンテーブルでnode=node->nextでポインタを後方に移動し、その後の具体的な分析で重要なコードを
後ろにコメントが付いています.次のdummyチェーンテーブルは新しい秩序チェーンテーブルであり、headチェーンテーブルは元のチェーンテーブルである.秩序チェーンテーブルに戻るために、
dummyチェーンテーブルのヘッダノードdummyは動いていませんが、nodeポインタを定義しています.headチェーンテーブルでは元のチェーンテーブルに戻る必要はありません.
従って直接headをポインタとして順次下へ移動し(headポインタに戻るにはヘッダノードを保存する必要がある)、nodeポインタは
dummyチェーンテーブルの中で絶えず下に移動するポインタ、headポインタはheadチェーンテーブルの中で絶えず下に移動するポインタです.
3.コード
/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */class Solution { public: /** * @param head: The first node of linked list. * @return: The head of linked list. */ ListNode *insertionSortList(ListNode *head) { //write your code here ListNode *dummy=new ListNode(0); while(head!=NULL) { ListNode *node=dummy; while(node->next!=NULL && node->next->valval) {node=node->next;/*nodeポインタを後ろに移動し、headチェーンテーブルの数より大きいものを見つけるまで、この数をdummyチェーンテーブルに追加します*/}ListNode*temp=head->next;/*headを元のチェーンテーブルのポインタとして順番に下に探して、whileループを飛び出したときに調べたこのheadはnodeより優れている.next大*/head->next=node->next;//ヘッドをnodeに挿入するnext前node->next=head;//ヘッドをnodeに挿入した後、ヘッドをnodeとnodeに挿入します.next間head=temp;//元head.nextは新しいheadとなってループ検索を継続}return dummy->next; } };
4.まとめ
チェーンテーブルを操作するときに大きな特徴があります.head->nextの変化は必ず最後にしなければなりません.headノードが与えられた場合
head->nextはランダムに決定され、head->nextは次のノードであるが、このノードを早すぎると見つからない.
赤字部分コードもhead->nextをtempに保存し、その後一連の操作をした後head->nextのアドレスが変更され、
しかしtempは元headの次のノードを残した.
同時に、単一チェーンテーブルはnextで支持され、新しい要素を挿入すると、2を1と3に挿入すると、元の関係は1->next=3である.
挿入後は1−>next=2,2−>next=3となり,前の2つのノード間の関係を断ち切った上で新しい2つの関係を確立する.
挿入ソートによるチェーンテーブルのソート
サンプル
Given
1->3->2->0->null , return 0->1->2->3->null 2.分析
挿入ソートは、配列の挿入ソートと同様に、チェーンテーブルの挿入ソートに関する一般的なソート方法の1つです.
原題はheadをヘッダノードとするチェーンテーブルを与え、次に秩序あるdummyチェーンテーブルを新規作成し、headチェーンテーブルを
のノードをdummyチェーンテーブルにそれぞれ挿入してheadチェーンテーブルのソートを完了します.順序付きチェーンテーブルで順次下に検索することを想定
元のチェーンテーブルの値と比較して、秩序チェーンテーブルの値が元のチェーンテーブルの値より大きい場合、その値を秩序チェーンテーブルに挿入します.例を挙げると
秩序チェーンテーブルには1、3があり、元のチェーンテーブルには2があります.1と2は先に比較して、1は2より小さくて、引き続き下へ探して、3は2より大きくて、この時元のチェーンテーブルを
の2を1、3の間に挿入して、最終的に秩序チェーンテーブル1、2、3を得る.
シーケンスチェーンテーブルでnode=node->nextでポインタを後方に移動し、その後の具体的な分析で重要なコードを
後ろにコメントが付いています.次のdummyチェーンテーブルは新しい秩序チェーンテーブルであり、headチェーンテーブルは元のチェーンテーブルである.秩序チェーンテーブルに戻るために、
dummyチェーンテーブルのヘッダノードdummyは動いていませんが、nodeポインタを定義しています.headチェーンテーブルでは元のチェーンテーブルに戻る必要はありません.
従って直接headをポインタとして順次下へ移動し(headポインタに戻るにはヘッダノードを保存する必要がある)、nodeポインタは
dummyチェーンテーブルの中で絶えず下に移動するポインタ、headポインタはheadチェーンテーブルの中で絶えず下に移動するポインタです.
3.コード
/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */class Solution { public: /** * @param head: The first node of linked list. * @return: The head of linked list. */ ListNode *insertionSortList(ListNode *head) { //write your code here ListNode *dummy=new ListNode(0); while(head!=NULL) { ListNode *node=dummy; while(node->next!=NULL && node->next->valval) {node=node->next;/*nodeポインタを後ろに移動し、headチェーンテーブルの数より大きいものを見つけるまで、この数をdummyチェーンテーブルに追加します*/}ListNode*temp=head->next;/*headを元のチェーンテーブルのポインタとして順番に下に探して、whileループを飛び出したときに調べたこのheadはnodeより優れている.next大*/head->next=node->next;//ヘッドをnodeに挿入するnext前node->next=head;//ヘッドをnodeに挿入した後、ヘッドをnodeとnodeに挿入します.next間head=temp;//元head.nextは新しいheadとなってループ検索を継続}return dummy->next; } };
4.まとめ
チェーンテーブルを操作するときに大きな特徴があります.head->nextの変化は必ず最後にしなければなりません.headノードが与えられた場合
head->nextはランダムに決定され、head->nextは次のノードであるが、このノードを早すぎると見つからない.
赤字部分コードもhead->nextをtempに保存し、その後一連の操作をした後head->nextのアドレスが変更され、
しかしtempは元headの次のノードを残した.
同時に、単一チェーンテーブルはnextで支持され、新しい要素を挿入すると、2を1と3に挿入すると、元の関係は1->next=3である.
挿入後は1−>next=2,2−>next=3となり,前の2つのノード間の関係を断ち切った上で新しい2つの関係を確立する.