Javaチェーンサーフェステストの質問

このメモは、それぞれのコードがそれ自体で書かれていると同時に、「剣ポイントオファー」のリンクリストに関連する説明をレビューしました。筆記試験とインタビューについての情報があることを望んでいます。

この記事には、リンクリストの次の内容が含まれています。

1。単一のリンクリストの作成とトラバーサル

2。単一のリンクリストでノードの数を見つけます

3.単一のリンクリストでk-lastノードを見つけます（提供する剣、質問15）

4.単一のリンクリストで中間ノードを見つけます

5. 2つの順序付けられた単一のリンクリストをマージすると、結合されたリンクされたリストがまだ順番に[発生の高頻度]（オファーによるステップ、質問17）

6.単一リンクリストの逆転[発生の最も高い頻度]（オファーによるステップ、質問16）

7.終わりから最初から最初のリンクされたリストを印刷します（提供する剣、質問5）

8。単一のリンクリストにリングがあるかどうかを判断します

9。リンクリストのリングの長さを取り出します

10。単一のリンクリストで、リングの出発点を取り出します（剣が提供する剣、質問56）。この質問は、上記の質問8と9を使用する必要があります。

11. 2つの単一リンクリスト間の交差点の最初の交差点を決定します（提供する剣、質問37）

1。単一のリンクリストの作成とトラバーサル：

 public class linklist {public node head; //リンクリストにデータを追加する（intデータ）ヘッダーノードが空になっている場合、リンクリストはまだ作成されていませんノードと現在のノードに配置します（新しいノードをリンクリストと相関させます）next = newノード（データ）; /この操作が完了した後、ノードは新しく追加されたノードを指します}} //メソッド：リンクリストをトラバースします（リンクリストを印刷します。メソッドのパラメーターは、トラバーサルがノードノードのパブリックボイドプリントから始まることを示します（ node node）{node == null）{current！= null; {//ここでの2つのメンバー変数の権限は、このクラスのみにアクセスできるため、プリバートにすることはできません。 data = data;} public static void（string [] args）{new linklist（）; ）;} list.print（list.head）; //ヘッドノードから出力を通過し始めます}}

上記のコードでは、ここのノードノードは内部クラスを使用してそれを表現します（33行目）。内部クラスを使用することの最大の利点は、外部クラスでお互いのプライベートオペレーションにアクセスできることです。

注：内部クラスアクセスの特性は、内部クラスを含む外部クラスのメンバーに直接アクセスできます。

追加およびトラバーサル操作を容易にするために、LinkListクラスにメンバー変数電流を追加して、現在のノードのインデックスを表します（行03）。

リンクリストを通過する方法（20行目）では、パラメーターノードはノードノードから開始することを意味し、必ずしもヘッドノードからトラバースする必要はありません。

2。単一のリンクリストでノードの数を見つけます。

リンクされたリストが空であるかどうかを確認するために注意してください。時間の複雑さはo（n）です。これは比較的簡単です。

コアコード：

 //シングルリンクリストの長さを取得します（ノードヘッド）{head == null）{return 0;長さ= current.next;

3.単一のリンクリストでk-lastノードを見つけます。

3.1通常のアイデア：

まず、リンクリスト全体を最初から最後まで反復し、リンクリストの長さのサイズを計算し、リンクリストの長さを取得しますリンクされたリストは空、kは0、kは1、kはリンクリストのノードの数より大きい

）。時間の複雑さはo（n）であり、一般的なアイデアは次のとおりです。

 public int findlastnode（int index）{//インデックスのノードは終了のためのノードを表します。 current = while！= null）{current.next; i <index; current.next;

インタビュアーがリンクリストの長さを横断することを許可しない場合はどうすればよいですか？次はです。

3.2改善のアイデア：（このアイデアは他の質問でも使用されています）

ここでは、2つのポインターを宣言する必要があります。つまり、2つのノードタイプの変数を最初に、最初のノードと2番目のノードにします。 1番目と2番目はK-1位置で区切られ、2つのノードが2番目のノードが最後のノードに到達するまで後方に移動します。最初のノードで指された位置は、最後のノードの位置です。ノード。時間の複雑さはo（n）です

コード実装：（最初のバージョン）

 public node findlastnode（node index）{node == null）{null} node = head; 0; i ++）{second.next; = second.next;

コード実装：（最終バージョン）（リンクリストのノードの数よりもKが多い場合、例外をスローします）

上記のコードでは、関数が実装されているようですが、十分に堅牢ではありません。

Kが0に等しい状況に注意してください。

Kがリンクリスト内のノードの数よりも大きい場合、nullポインターの例外が報告されるため、ここでは判断が必要です。

コアコードは次のとおりです。

 public node findlastnode（int k）{k == 0 || null）{null; （int i = 0; i <k -1; i ++）{system.out.println（ "i's value is"+i）; kの値はリンクリストの長さよりも大きい//新しいnullpointerexception（ "リンクリストの長さは" + kよりも少ない）。 null; 2番目のノードは、この時点で最後のノードに到達します。

4.単一のリンクリストで中間ノードを見つけます。

同様に、インタビュアーは、リンクリストの長さを計算することはできません。

アイデア：

上記の2番目のセクションと同様に、2つのポインターが1番目と2番目に設定されていますが、ここでは2つのポインターが同時に前進し、2番目のポインターは毎回2つのステップを踏み、最初のポインターは2番目のポインターが到達するまで毎回1つのステップを踏みます最後のノードでは、最初のポインターで指されたノードは中間ノードです。リンクされたリストは空で、リンクリストのノードの数は1と2であることに注意してください。時間の複雑さはo（n）です。

コード実装：

 //リンクリストの中間ノードPublic Node FindMidNode（ノードヘッド）{head == null）{null; 2番目のエンドは2桁で、最初のノードは1つを移動します（second！= null && next！= null）{first = second.next.next;この時点で、最初のポインターが指し示す位置は、最初に中間ノードの位置です。

上記のコードでは、nが偶数である場合、得られた中間ノードはn/2 + 1ノードです。たとえば、リンクリストに6つのノードがある場合、4番目のノードが取得されます。

5. 2つの順序付けられたシングルリンクリストをマージすると、リンクされたリンクされたリストがまだ順調です。

この質問は、多くの場合、さまざまな企業によって調査されます。

例えば：

リスト1：

1-> 2-> 3-> 4

リスト2：

2-> 3-> 4-> 5

マージの後：

1-> 2-> 2-> 3-> 3-> 4-> 4-> 5

解決策のアイデア：

リンクリスト1とリンクされたリスト2を互いに比較します。

これは、マージソートに似ています。両方のリンクされたリストが空で、そのうちの1つが空である状況に特に注意してください。 O（1）スペースのみが必要です。時間の複雑さはo（max（len1、len2））です

コード実装：

 // 2つのパラメーターは、2つのリンクリストのヘッダーノードを表しますパブリックノードMERGELINKLIST（ノードヘッド、ノードヘッド2）{if（head1 == null && head2 == null）{// if（head2 == null）{return head1} //最初に、現在のノードがhead1とhead2の小さなデータを指し、head1.data <head2.data）{head = head1;次へ} head2; head2; head2.next; ; //現在のポインターの次のノードは、current.nextに対応していますcurrent.next; head2 .next; （head2！= null）{//リンクされたリスト1は、empty.next = head2;

コードテスト：

 public static void main [] rinklist list1 = new linklist（）; （i）; ）; // list2をマージし、list3 list3.print（list3.head）;

上記のコードで使用される追加方法と印刷方法は、サブセクション1と一致しています。

ランニング効果：

注：このソリューションは、「剣ポイントオファー」で再帰的であり、理解するのが少し難しいと感じています。

6。単一リンクリストの反転：[発生の最も高い頻度]

たとえば、リンクリスト：

1-> 2-> 3-> 4

反転の後：

4-> 2-> 2-> 1

アイデア：

元のリンクリストを最初から端まで繰り返し、各ノードが通過し、削除され、新しいリンクリストのフロントエンドに配置されます。リンクされたリストは空で、ノードは1つしかないことに注意してください。時間の複雑さはo（n）です

方法1 ：（トラバーサル）

 //メソッド：リンクリストの逆転パブリックノードリバーサリスト（ノードヘッド）{//リンクリストが空の場合、またはノードが1つしかない場合、反転は必要ありません。元のリンクリストのヘッドノードは直接返されます。元のリンクリスト（head.next == null）{node node = null;反転後の新しいリンクリストのヘッダー{next = current.next;新しいリンクリストのヘッダーノードreversehead = next;

上記のコードでは、コアコードは16行目と17行です。

方法2 ：（再帰）

この方法は少し難しいので、今のところは話しません。

7.端から端まで単一のリンクリストを印刷します。

この種の反転順序のために、最初に、最初にアウトするスタックについて考える必要があります。したがって、この質問は自分でスタックを使用するか、システムがスタック、つまり再帰的なものを使用させます。リンクされたリストが空の場合に注意してください。時間の複雑さはo（n）です

注：最初に単一のリンクリストを逆にしてから、出力を通過することを考えないでください。

方法1 ：（自分で新しいスタックを作成します）

 //メソッド：端から端までのリンクされたリストを印刷しますvoid reverseprint（node head）{head == null）{return} stack = new stack <node>（）;新しいスタックのcur rent = headを作成します。 //スタックを押しますwhile（stack.size（）> 0）{system.out.println（stack.pop（）。データ）;

方法2 ：（システムのスタックを使用：再帰的でエレガントで簡潔なコード）

 public void reverseprint（node head）{head == null）{return.thext.out.println（head.data）;

概要：方法2は、再帰の実装に基づいていますが、ダイアンは簡潔でエレガントに見えますが、リンクされたリストが非常に長い場合、メソッド呼び出しが非常に深くなり、スタックオーバーフローを引き起こす可能性があります。方法1の明示的なスタックはループに基づいて実装され、コードはより堅牢です。

8。単一のリンクリストにリングがあるかどうかを判断します。

ここでは、2つのポインターもリングがある場合、トラバースへのポインターを使用することは決して終わりません。

したがって、2つのポインターを使用して、最初のポインターは一度に1つずつ、2番目のポインターが1つのポインターと2番目のポインターが出会う場合、リングがあることを意味します。時間の複雑さはo（n）です。

方法：

 //単一のリンクリストには、パブリックブールハスサイクル（ノードヘッド）があるかどうかを決定します）{first = first.next;リングはtrueを返します。

フルバージョンコード：（テストパーツを含む）

ここでは、オーバーロードされた追加（ノードノード）メソッドを追加する必要があります。これは、一元配置リンクリストを作成するときに使用する必要があります。

 linklist.java：public class linklist {public node head; ll）{ / /ヘッダーノードが空になっている場合、リンクリストがまだ作成されていないことを意味します。次に、ヘッダーノードヘッドに割り当てられています。新しいノードを作成し、現在のノードの後ろに配置します（新しいノードをリンクリストと相関させます）next = newノード（データ）; ;メソッドオーバーロード：リンクリストにノードを追加する（ノードノード）{node == null）{return; ; else.n ext = current.next; node node）{node == null）{current！= null;方法：単一のリンクリストには、パブリックブールハスサイクル（n odeヘッド）があります{head == null）{return false; first = first.next;リストはtrueを返します。 int data; （int i = 0; i <4; i ++）{list.add（i）}のデータを追加する（list.head）;リンクリストのループです。注：この時点で得られたリングの構造は、次のセクション8の図1の構造です。 system.out.println（list.hascycle（list.head））;

単一のリンクリストにリングがあるかどうかを検出するコードは、行50です。

88行目：ヘッダーノードをリンクリストに追加し続けると、この時点で単一のリンクリストがループされます。最終的なランニング効果は真です。

88行のコードが削除されている場合、現時点では単一のリンクリストにはループがなく、実行効果は偽です。

9.リングリンクリスト、リングの長さを取り出します。

通常遭遇するリンクリストは次のとおりです。（図1）

上の写真のリングの長さは4です。

しかし、以下も次のとおりである可能性があります：（図2）

この時点で、上の写真のリングの長さは3です。

では、リングの長さをどのように見つけますか？

アイデア：

ここでは、最初に上記のセクション7でハスサイクルメソッドを使用する必要があります（リンクリストにリングがあるかどうかを判断する方法）が、このメソッドをわずかに変更するには、このメソッドがブール値であるかどうかを判断する必要があります。私たちが出会うノードの値を返します。次に、このノードがリングにある必要があるノードを取得できます。

方法：

 //メソッド：単一のリンクリストにリングがあるかどうかを判断します。返されたノードは、パブリックノードハスサイクル（ノードヘッド）を満たしています.next; second.next.next; null ;/メソッド：リングの長さを取得するリングリンクリストがあります。パラメーターノードは、public int getcyclelenty（node node）{return 0; current.next ++;

フルバージョンコード：（テストパーツを含む）

 public class linklist {public node current;ノードは空で、リンクリストがまだ作成されていないことを意味し、ヘッダーノード= new Node（data）に割り当てます}。現在のノード（新しいノードをリンクリストと相関させます）next = newノード（//リンクリストの現在のインデックスを1つずつ移動します。現在のノードは、新しく追加されたノードを指します}} //メソッドオーバーロード：リンクリストにノードを追加（ノードノード）{if（node == null）{return; {head = current = current = current.next; Node Node public void print（node node）{node == null）{current！= null）{system.out.println（current.data）; current.next; first = head; while！= null）リンクリストは、最初にリングのようなリターンです。パラメーターノードは、public int getcyclelenty（node node）{return 0; current.next ++;プライベート、プライベートの許可はこのクラスにのみアクセスできるためです。 int data; = null; //（int i = 0; i ++）{list1.add（i）; ; // 2番目のノードを切り取ります} list1./ //リンクリストの2番目のノードを指しますプロセスは、このセクションの図2の構造ですcurrent = list1.hascycle（list1.head）; ））;

ランニング効果：

上記の行104〜122のテストコードが次のように変更された場合：（つまり、図2の構造を図1の構造に変更します）

 public static void main（string [] args）{linklist 1 = new linklist（）; （List1.head）;注：この時点で得られたこのリングの構造は、このセクションの図1の構造です。ノードcurrent = list1.hascycle（list1.head）;

結果の実行：

上記のコードで8行を削除すると、リンクされたリストにはループがないため、実行の結果は0です。

10。単一のリンクリストでは、抽出されたリングの開始点：

通常遭遇するリンクリストは次のとおりです。（図1）

上の写真のリングの開始点1。

しかし、以下も次のとおりである可能性があります：（図2）

この時点で、上の写真のリングの出発点は2です。

方法1：

ここでは、上記のセクション8のリングの長さを取り出してgetcyclelengthの方法を使用し、この方法を使用してリングの長さを取得する必要があります。リングの長さを取得した後、最初に2番目のポインターを使用する必要があります会うとき、彼らが出会うときの結び目。

注：リングの出発点を見つけるには、最初にリングの長さを取得する必要があり、リングの長さを取得するには、最初にリングがあるかどうかを判断する必要があります。したがって、ここでは実際には3つの方法が使用されています。

コード実装：

方法1のコアコード：

 //メソッド：リングの開始点を取得します。パラメーターの長さは、リングの長さを表します（int i = 0; i <cyclelength; i ++）{second = second.next; ！= null）{first.next; second.next; nullを返します。

フルバージョンコード：（テストパーツを含む）

 public class linklist {public node current;ノードは空で、リンクリストがまだ作成されていないことを意味し、ヘッダーノード= new Node（data）に割り当てます}。現在のノード（新しいノードをリンクリストと相関させます）next = newノード（//リンクリストの現在のインデックスを1つずつ移動します。現在のノードは、新しく追加されたノードを指します}} //メソッドオーバーロード：リンクリストにノードを追加（ノードノード）{if（node == null）{return; {head = current = current = current.next; Node Node public void print（node node）{node == null）{current！= null）{system.out.println（current.data）; current.next; first = head; while！= null）リンクリストは、最初にリングのようなリターンです。パラメーターノードは、public int getcyclelenty（node node）{return 0; current.next ++;パラメーターの長さは、リングの長さを表します（int i = 0; i <cyclelength; i ++）{second = second.next; ！= null）{first.next; second.next; nullを返します}クラスノード{//注：プライベートの許可はこのクラスにのみアクセスできるため、当時の2つのメンバー変数の許可はプライベートできません。 int data; = null; //（int i = 0; i ++）{list1.add（i）; ; // 2番目のノードを切り取ります} list1./ //リンクリストの2番目のノードを指しますこのセクションの図2の構造= list1.hascycle（list1.head）; .out.println（ "リングの開始点は" + list1.getCyclestart（list1.head、length）.data）;

11. 2つの単一リンクリストが交差する最初の交差点を決定します。

「プログラミングの美しさ」P193、5.3、インタビュー質問37にはこの質問があります。

インタビューでは、この質問に遭遇したときの多くの人々は、最初のリンクリストで各ノードを通過します。 2番目のリンクリストにノードがある場合、最初のリンクリストのノードと同じように、2つのリンクリストがこのノードでオーバーラップすることを意味します。明らかに、この方法の時間の複雑さはo（len1 * len2）です。

方法1：スタックを使用するというアイデア

一般的なノードと部分的に重複する2つのリンクされたリストを見ることができます。トポロジーの形状はYのように見えますが、X字型のリストではありません。 下の図に示すように：

上の図に示すように、単一のリンクリストに共通ノードがある場合、最後のノード（ノード7）は同じでなければならず、中央の特定のノード（ノード6）から始まり、後続のノードは同じです。

問題は、単一のリンクリストで、最初のノードから順番にしか通過できず、最終的にエンドノードに到達できることです。到達する最終的なテールノードは、最初に「最初から終了」のように聞こえますか？したがって、この問題を解決するためにスタックの特性を使用することを考えることができます。2つのリンクされたリストのノードを2つのスタックのエンドノードが2つのスタックの上部に配置します。最後の同一のノードが見つかるまで、スタックの上部を比較しましょう。

このようにして、2つの補助スタックを使用する必要があります。スペースの複雑さはO（LEN1+LEN2）であり、時間の複雑さはO（LEN1+LEN2）です。最初のブルートフォース法と比較して、時間効率が改善されました。これは、時間効率のために空間消費を使用するのと同等です。

それで、より良い方法はありますか？次にそれについて話しましょう。

方法2：2つのリンクされたリストが交差する最初のノードを決定します。高速と遅いポインターを使用し、推奨されます（より最適なソリューション）

上記の方法2では、スタックを使用する理由は、2つのリンクされたリストのエンドノードに同時に到達するために移動することを望んでいるためです。其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走|len1-len2| 步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个交点。

这种思路的时间复杂度也是O(len1+len2)，但是我们不再需要辅助栈，因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候，就可以动手写代码了。

核心代码：

 //方法：求两个单链表相交的第一个交点public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = getLength(head1); int length2 = getLength(head2); int lengthDif = 0; //两个链表长度的差值Node longHead; Node shortHead; //找出较长的那个链表if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //将较长的那个链表的指针向前走length个距离for (int i = 0; i < lengthDif; i++) { longHead = longHead.next; } //将两个链表的指针同时向前移动while (longHead != null && shortHead != null) { if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //方法：获取单链表的长度public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length;

以上就是有关java链表的经典面试题目，希望可以帮助大家顺利通过面试。