1

2 つの単方向リンク リスト、サイズ m 、r で、2 番目のリンク リストの先頭の後に最初のリンク リスト ノードを挿入する必要があり、時間計算量はメソッドの O(1) である必要があります。

これは私にとって本当に興味深い難しい問題です。解決策を考えるたびに、時間の複雑さは O(m+r) です

これを解決するにはヒントが必要です。私はこの問題に無駄な労力を費やしました。

編集：

私がこれまでに持っているものを共有しましょう：

  1. 新しいリンク リストを作成する
  2. 2番目のリストのHEADを追加
  3. それでも O(1)
  4. 最初のリストのすべてのノードを追加します
  5. (n) になる

  6. 最初のリストから残りのノードを追加します

  7. 別になる (n-1)

アップデート：

これについてあなたはどう思いますか？ここで質問した直後にインスピレーションを得ました:) ここに画像の説明を入力

4

2 に答える 2

4

2 つの単方向リストがあり、最初のテールがまだない場合、これは O(n) でのみ可能です。末尾がある場合は、2 番目のリストの先頭を指すようにします...

編集: 2 番目のリストの先頭は、最初のリストの先頭を指します。2番目のリストの2番目のノードへの参照を保持します。最初のリストを下に繰り返します-開始するテールへの参照がない場合、これはO(n)です-そして、そのポイントのテールを2番目のリストの元の2番目の要素にします。

于 2012-10-15T18:39:37.697 に答える
0

これらの構造があると仮定します：

  • リスト
    • ヘッド ノード
    • テール ノード
  • ノード
    • 価値
    • 次のノード

自分へのリマインダー: 目標は、「2 番目のリンク リストの先頭の後に最初のリンク リスト ノードを挿入する」ことです。

その後、あなたがしなければならないことは次のとおりです。

// Hook up the end of list1 to the original second element of list2
list1.tail.next = list2.head.next;
// Set the second element of list2 to be the first element of list1
list2.head.next = list1.head;

List2 は以前と同じ場所で終了します (テール ノードは同じです)。

list1「フローティング」ヘッドができましたが、これは一般的に悪いニュースです...しかし、反復するとlist1、両方の元のリストからすべての要素が取得されます...

于 2012-10-15T19:09:04.137 に答える