2


筆記試験で、次のような問題が出題されました。

前半と後半の両方が独立してソートされた整数リンクリストが与えられます。2 つの部分をマージして 1 つの並べ替えられたリンク リストを作成する関数を記述します。

制約: 余分なスペースを使用しないでください。

テスト ケースと出力:
入力 List1 :
4->5->6->7->1->2->3;
出力:
1->2->3->4->5->6->7

入力 2:
5->6->7->8->1->2->3->4;
出力 2 :
1->2->3->4->5->6->7->8

私が考えることができるのは、前半のトラバーサル用と後半のトラバーサル用の 2 つのポインターを使用することです。それらを使用して、先頭から中央 (1 番目のポインターを使用) と中央から最後 (2 番目のポインターを使用) にトラバースできます。両方の部分を同時にトラバースしながら、値を比較し、必要に応じて交換できます。

ただし、このソリューションでは、メモリを消費する 2 つのポインターを使用します。

メモリを使わずに実行できますか？

筆記試験なので、説明を求めることはできません。
ご協力をお願いいたします。ありがとう。

4

1 に答える 1

4

「余分なスペースを使用しない」という場合、ポインターやスカラーを意味するものではありません。それらは「配列」と「動的に割り当てられた構造」を意味します。あなたの場合、メモリ量は固定されています。

next順序付けされた 2 つのリストをマージするのは簡単です。最初にリストを半分に切り、次にその要素のポインタを再配置して、リストをソートします。

newHead、head1、およびの3 つのポインタが必要ですhead2。

  • 初期化head1しhead2てhead元のリストへ
  • 並べhead2替えられたシーケンスにブレークが表示されるまで (つまり、head2->next->valueが より小さい場合head2->value) 進みます。head2->nextに設定してリストを切り取りNULLます。オリジナルを維持してhead2->nextください - それはあなたの新しいものですhead2

この時点で、独立して順序付けられた 2 つのリンクされたリストがあり、従来のマージ アルゴリズムを適用できます。またはnewHeadの小さい方の要素に設定し、ループ内を移動して、現在の最後の要素のポインターをorの小さい方に設定します。またはを押したら、最初に要素を使い果たしたリストの に、他のリストの先頭を割り当てます。これで、ソートされたリストの先頭を指します。head1head2nexthead1head2head1->next == NULLhead2->next == NULLnextnewHead

于 2012-12-21T11:33:33.363 に答える