筆記試験で、次のような問題が出題されました。
前半と後半の両方が独立してソートされた整数リンクリストが与えられます。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 つのポインターを使用します。
メモリを使わずに実行できますか?
筆記試験なので、説明を求めることはできません。
ご協力をお願いいたします。ありがとう。