チェーンテーブルシリーズタイトル

1.2つの整列チェーンテーブルの共通部分を印刷する
【タイトル】2つの整列チェーンテーブルのヘッダポインタhead 1とhead 2を与え、2つのチェーンテーブルの共通部分を印刷する.例えば、【考え方】チェーンテーブルが整然としているため、2つのポインタが同時に始まり、1つずつ比較し、小さい人は後ろに移動し、等しい場合は印刷し、一緒に後ろに移動します.
2.チェーンテーブルが返信構造であるか否かを判断する
【タイトル】チェーンテーブルのヘッダノードheadを指定し、チェーンテーブルが返信構造であるか否かを判断してください.たとえば、1->2->1でtrueを返します.1->2->2->1、trueを返します.15->6->15、trueを返します.1->2->3でfalseを返します.【考え方】

方法1:チェーンテーブルを遍歴し、値をスタックに順次入力する.回文は正の遍歴=逆の遍歴であるからである.再度チェーンテーブルを遍歴し、同時にスタックが順次ポップアップされ、ずっと等しい場合は、返事です.

方法2:(スタックの空間が半分に減った)2つのポインタ、1つは速くて遅くて、1つは1歩歩いて、1つは2歩歩いて;速いポインタが歩き終わると、遅いポインタはその後に遍歴した数字が順次スタックに入る.それから再びポインタを最初から遍歴して、同時にスタックが順番に飛び出して、ずっと等しいならば、返事です.

【ステップ】チェーンテーブル長がNである場合、時間的複雑度がO(N)に達し、余分な空間的複雑度がO(1)に達する.【考え方】2つのポインタ、1つは速くて遅くて、つまり1つは1歩、1つは2歩歩きます;速いポインタが終わった後、遅いポインタはその後に遍歴した数字でreverseを行う.それから両端から同時に遍歴して、ずっと同じなら、回文です.
3.一方向チェーンテーブルをある値で左が小さく、中間が等しく、右が大きい形に分ける
【テーマ】

は、一方向チェーンテーブルのヘッダノードheadを与え、ノードの値タイプは整数pivotを与える.

はチェーンテーブルを調整する関数を実現し、チェーンテーブルを左部分がpivot未満のノードであり、中間部分がpivotに等しいノードであり、右部分がpivotより大きいノードであるように調整する.この要件を除いて,調整後のノード順序にはこれ以上の要件はない.

は、例えば、チェーンテーブル9−>0−>4−>5−>1、pivot=3である.調整後のチェーンテーブルは、1−>0−>4−>9−>5であってもよいし、0−>1−>9−>5−>4であってもよい.

要するに、左を満たすノードはすべて3未満のノードであり、中間部分はすべて3に等しいノード(この例ではこの部分は空)であり、右部分はすべて3以上のノードであればよい.一部の内部のノードの順序は要求されません.

【考え方】

は、あるブロックがない場合を考慮する必要があります.

方法1:3つのキューを用意し、チェーンテーブルを遍歴し、ノードを対応するキューに入れ、順番にキューを出ればよい.

方法2:チェーンテーブルを遍歴し、pivotより小さい、等しい、および大きい最初のノードをそれぞれ見つける.次に、3つのノードをそれぞれヘッダノードとして、対応するノードに出会ったらその中に入れます.最後に3つのチェーンテーブルの先頭と末尾を接続すればいいです.

4.ランダムポインタノードを含むチェーンテーブルのコピー
【タイトル】特殊なチェーンテーブルノードクラスは以下のように記述される.

public class Node {
  public int value;
  public Node next;
  public Node rand;
  public Node(int data) {
    this.value = data;
  }
}

Nodeクラスのvalueはノード値であり、nextポインタは通常の単一チェーンテーブルのnextポインタと同様に次のノードを指し、randポインタはNodeクラスに追加されたポインタであり、このポインタはチェーンテーブルのいずれかのノードを指し、nullを指す可能性がある.

Nodeノードタイプからなるループレス単一チェーンテーブルのヘッダノードheadを指定します.このチェーンテーブル内のすべての構造のコピーを完了し、コピーした新しいチェーンテーブルのヘッダノードを返す関数を実装してください.

【ステップアップ】追加のデータ構造を使用せず、有限数の変数のみを使用し、時間的複雑度O(N)内で元の問題を実現する関数を完了する.【考え方】

方法一:経典解法、map

方法2:ノードをクローンするときは、古いノードの後ろに置く、クローンノードのrandomは古いノードに対応するrandomを指す.next.その後分離を行い,クローンチェーンテーブルを得,分離時にrandomポインタを考慮する必要はない.

5.2つの単一チェーンテーブルが交差する一連の問題
【テーマ】

本題では、単一チェーンテーブルにループがあるか、ループがないかのいずれかです.2つの単一チェーンテーブルのヘッダノードhead 1およびhead 2が与えられ、この2つのチェーンテーブルは交差するか、交差しないかのいずれかである.

関数を実装してください.2つのチェーンテーブルが交差している場合は、交差する最初のノードに戻ります.交差しない場合はnullを返します.

【要件】チェーンテーブル1の長さがN、チェーンテーブル2の長さがMの場合、時間的複雑度はO(N+M)、余分な空間的複雑度はO(1)に達してください.【考え方】

チェーンテーブルにループがあるかどうかを判断し、ループがある場合は、最初のループに入ったノードを返します.

方法1:チェーンテーブルを遍歴し、各ノードをmapに追加し、1つのノードがmapに追加される前にmapにすでに存在していることを発見したら、ループがあることを説明し、このノードはループノードである.最後にnullに着いたら、リングがないことを説明します.

方法2:2つのポインタ、1つは速くて遅くて、1つは1歩歩いて、1つは2歩歩いています.リングがなければ、速いポインタは必ず終わりまで行きます.ループがあれば、速いポインタと遅いポインタは必ずループの中で出会って、出会った後、速いポインタはheadノードに戻って、それから速いポインタと遅いポインタはすべて1歩歩くたびに変わって、同時に歩き始めて、きっとループに入るノードで出会って(数学の結論).

両者が交差するのは3つの状況に分かれている.

の場合1:2つの単一チェーンテーブルにリングがありません.まず2つのチェーンテーブルの長さを取得し、差を求める.2つのポインタで、長いチェーンテーブルのポインタは差のステップ数を先に行って、それから同時に行きます.last 1=last 2がそれらが必ず交差していることを示している場合、そうでなければ交差しません.

の場合2:1つのチェーンテーブルにリングがあり、1つのチェーンテーブルにリングがなく、絶対に交差することはできません.1つのノードにnextが1つしかないからです.

の場合3:両方のチェーンテーブルにリングがあります.

の2つのチェーンテーブルは、リングが現れる前に交差し、その後ずっと交差しています.loop 1=loop 2、すなわち2つのチェーンテーブルのループノードが同じであれば交差する.2つのポインタで、長いチェーンテーブルのポインタは差のステップ数を先に行って、それから同時に行きます.2つのチェーンテーブルのインループノードが空で等しくない場合、交差します.

の2つのチェーンテーブルはリングのみを共有します.loop 1リングを歩いている間にloop 2に遭遇しましたが、等しくありません.

6.一方向および双方向チェーンテーブルの反転
【課題】反転一方向チェーンテーブルと反転双方向チェーンテーブルの関数をそれぞれ実現する.【要件】チェーンテーブル長がNの場合、時間的複雑度はO(N)、余分な空間的複雑度はO(1)である.【考え方】スタックまたはその場で反転できます.