👻
連結リストの後半分を逆順にする方法
問題文
下記はマサチューセッツ工科大学オープンコースウェア(MIT OCW)2010年度の「計算機科学のための数学」に出題する問題の要約:
近くの学校の生徒がアイスクリームトラックに殺到する。
一台では追いつけないため、生徒の列の最後にもう一台のトラックがくる。
だが、生徒たちは納得が行かない:これでは一番遅かった人が先にアイスクリームをもらう!
代わりに、列の後半に立つ生徒はみんな逆順になればいいと決断される。
「生徒を表す長さ
第一候補者
リストを最後まで渡り、それぞれN
、P
、そして最後の要素にlast
ポインターを設置する(last
はこのステップでしか使用しない):
P
以降のリストを真逆にする:
これでリストの後半分の順番は一見正しく見えるが、逆方向になっているのでこれではリストがlast
で終わってしまう。
今度はP
を使って連結方向を正す。
- まず、
P
の後ろにくる要素への参照をP2
に保存する:
-
P2
からP
を参照:
-
P
からP2
へのポインターを削除:
-
P
をP2
にする:
ご覧の通り、最後の要素二つの方向の修正が完成した。同じ手順を次の要素に適用すれば正解が出るわけだが、ちょっとした問題点がある:ステップ2〜4でP2
は同時にP
と次の要素を指している。つまり、P2
に二つ目のポインターを与えないといけない。
また、リストの後半分を二度も通ってしまう。
というわけで、より適切なアルゴリズムを見てみよう。
第二候補者
元のリスト:
「❌」は最後のnullノードを表す。
- まず
目要素への参照をPに代入する:n+1
このPは一回しか代入しないので、これからNからだんだん離れていく。
- 次に
目要素へのポインタP2を作成。n+1
Pと違ってP2いつも
- Nの次を
1
にする:
- Pの指しているノードの次を
2
にする:
お気づきかと思いますが、「PとP2の次」ではなく、「Pの次」ですね。今、PとP2はたまたま一致しているわけだが、この状況は長く続かない。
- では、
1
の次をP2(Pではなく)にする:
そしてP2を
同じステップを繰り返すと:
もう一回:
完成です。
比較
1番目:
- リストの最後までいく:2n
- n回:
- P2作成
- P2からPへの追加ポインタ
- PからP2へのポインタ削除
- P2をPに代入
合計:
2番目:
- n番目までいく:n
- n回:
- P2作成
- Nの次を変更
- Pの次を変更
-
の次をP2にするn+1
合計:
結論
二番目の方はちょっと早いかな。漸近式はいずれも
Discussion