0

私はインタビューでこれを尋ねられました。

リストは次のようになります。

a 1- > b n- > a 2- > b n-1 ...- > a n- > b 1- > NULL

そのような、a 1 <a 2 <... <a n

と

b 1 <b 2 <... <b n

インタビュアーは私に次の制約を課しました：

  1. リストを適切に並べ替える必要があります。つまり、要素のグループの代替要素を別のリストに削除することはできません。
  2. 単純な並べ替えアルゴリズムよりも、リストにあるパターンをどうにかして利用する必要があります。

面接中も今も解決策が思いつかなかった。:-(

編集：この単一リンクリストを並べ替えるコードをCで記述します。

Edit2：バブルソートからアイデアを借りて、そのパターンを利用できるとも言われました。しかし、それは「素朴な」短いものであってはなりません。

インタビュアーが人為的な制約を課すのは嫌いですが、ちょっと仕事は仕事です:-)

4

2 に答える 2

2

「リストを適切にソートする必要があります」この要件は私を混乱させます。私は自然な解決策は次のとおりだと思っていたでしょう：

  • リスト内の「次の」ポインタをジグザグして、2つのリストを作成します。1つにはaが含まれ、もう1つにはbが含まれます。
  • これらの2つのリストでマージを実行します。

しかし、最初のステップがルールに違反しているかどうかはわかりません。ノードやそのデータをコピーせず、実際にはデータも移動しないため、この用語を理解しているように「適切な場所」にあります。ただし、代替要素は別のリストに削除されます。

2つのステップを1つのパスに組み合わせる方法をすぐに考えることはできません。

[編集：ここで「インプレース」とは、リストを再リンクするのではなく、データを移動する必要があることを意味します。その場合、問題はもっと難しいと思います。効率的なインプレースマージソートは、（a）リンクリストで、（b）間違った順序で代替要素を使用して実行しようとせずに、配列で十分に苦痛を伴います]

于 2012-05-09T10:51:34.100 に答える
0

それを「所定の位置」に保つために、最初にリストをその場で次のように変換できます。

a 1- > ...- > a n- > b 1- > ...-> b n

リストをウォークスルーし、b要素を1つずつリストの最後に移動します。

この後、要素を「バブルソート方式」で1つずつ前方に移動できます。つまり、最初はb 1の前にある境界の後の場所が見つかるまで、前方にスキャンします。

しかし、私はその質問がかなり人為的なものであることに同意します。

于 2012-05-09T13:25:51.873 に答える