高速一方向リンクテーブル。
乾坤大諾儀の分析
問題
Kは非負の整数です。この問題は簡単なように見えますが、1つ問題があります。
例
1->2->3->4->5->6->null と K=3 が与えられます。
4->5->6->1->2->3->nullとなります。
分析
本題に戻り、簡単な考察を。
まず、細部を見てみましょう。
- =0
- Kがチェーンテーブルの長さに等しい場合はどうなりますか？
- Kがチェーンテーブルの長さより大きい場合はどうなりますか？
K=0に加えて、テール・ポインタを知る必要があることは明らかです。そこで最初のステップとして、チェーン・テーブルをスキャンしてテール・ポインタのtailとチェーン・テーブルの長さMを取得します。
次に、ノードへの新しいヘッド・ポインタを得るために必要な移動ステップ数を計算します。
次にテールをヘッドに、次にヘッドをpに、次にpをヌルに。
この解決法では、連鎖表を2回スキャンする必要があるかもしれません。連鎖表の長さMがあらかじめわかっていれば、2ポインタ法を使うことができるかもしれません：
2つのポインタがあり、最初のポインタはまずM-1ステップ進み、次に最初のポインタと2番目のポインタが一緒に進み、今度は最初のポインタが終点を指すまで進みます：
- 2番目のポインタが指す次のノードが新しいヘッドノードとして設定されます。
- 2番目のポインタが指すノードの次のポインタをnullに向けます。
- 最初のポインタが指すノードの次のポインタを、古いヘッドノードに向けます。
以下、似たような質問のバリエーションを例としてご覧ください。
n個の要素を持つ配列について int a[n]={...} ; mビットだけ配列の内容を周期的に左にシフトする効率的なアルゴリズムを書きなさい。配列の内容を循環的にmビット左シフトする効率的なアルゴリズムを記述します。例： int a[6] = {1,2,3,4,5,6} , 3ビットずつ左シフトして結果{456123}を得るループ。
アルゴリズムの基本的な考え方は以下の通り：
例からわかるように、1,2,3は配列の末尾に移動し、4から8までは3つ前に移動します。したがって、1,2,3を全体として考え、まず4,5,6と交換し、次に7,8と交換することが考えられます。
最初の交換の結果：4、5、6、1、2、3、7、8
7と8は2桁しかないので、2回目の交換は1,2,3の1,2のみで行います。結果は次のようになります：4, 5, 6, 7, 8, 3, 1, 2.
ご覧のように、最初の5ビットはすでに最終結果を満たしており、最後の3ビットだけがまだ最終結果を満たしていません。しかし、3, 1, 2を部分配列として見て、この部分配列を循環的に1ビット左にシフトすると、1, 2, 3になります。
したがって、左シフトされるmビットは、要素を移動するときに全体として見ることができます。
最後に、次のm個の要素はサブアレイとみなされ、m - n % mビットだけ循環的に左シフトされます。
このアルゴリズムの時間的複雑度はO(n)であり、最も基本的な巡回アルゴリズムのO(mn)よりも小さく、空間的複雑度はO(1)です。
