公式シリーズ - リートコード連鎖表のポイント＆問題まとめ

序文

relationresult私が初めてアルゴリズムのトピックをブラッシングする準備を始めた時、私は本当に難しいと感じ、10個のトピックのうち9個は知らないトピック。心には一万本の草泥馬が走っていて、どうしてこんなに熱い鶏肉になれるのでしょう。

アルゴリズムもまた、練習を重ねることで少しずつ成長していくものなのだと気づきました。

1. まず、基本的なデータ構造、配列、連鎖表、ハッシュ表、セット、バイナリツリー、ヒープ、スタックなどをマスターする必要があります。それらの長所と短所、適応のシナリオ、時間の複雑さと空間の複雑さを知る必要があります。また、単純なAPIを知ることもできません。
2. カテゴリー化されたブラシは、PowerButtonの上にあるように、タグごとに利用できます。例えば、連鎖リスト、配列、バイナリ検索、バイナリツリー、動的プログラミングなどです。
3. アルゴリズムの学習は一日にしてならず、長期的な積み重ねが必要です。お勧めの練習方法は、毎日1～2問をこなすことです。トピックは数ではなく、価値は理解にあります。1ヶ月、2ヶ月と続けることで、だんだんと調子が良くなってくるのがわかるはずです！

それでは、本日の本題である「リートコード連鎖表の知識ポイントと疑問のまとめ」に入りましょう。

知識

連鎖テーブルとは

リンクテーブルは一般的な線形構造です。連続したメモリ空間を必要とせず、ポインタによって連結できる散在したメモリブロックのセットを必要とします。メモリブロックが連鎖表のノードとなり、すべてのノードをつなぎ合わせるために、連鎖表の各ノードはデータを格納するだけでなく、連鎖表の次のノードのアドレスを記録する必要があり、ポインタの次のノードのアドレスのこのレコードは子孫ポインタと呼ばれます。連鎖表を検索するにはO(N)の時間複雑度が必要で、これは配列と似ていますが、連鎖表は配列のようにインデックスを付けることでO(1)の時間でn番目の数を読み取ることはできません。連鎖表の利点は、任意の位置のノードを高い効率で挿入または削除できることです。

カテゴリー

一方向リンクリスト

各ノードには、次のノードへのネクスト・ポインタと、値を格納するためのメンバ変数があります。一方向リンク・テーブルには、ヘッド・ノードとテール・ノードという2つの特別なノードがあります。ヘッド・ノードはリンクされたテーブルのベース・アドレスを記録するために使用され、ヘッド・ノードを知ることでリンクされたテーブル全体をたどることができます。テール・ノードはポインタがヌル・ポインタを指すので特別です。

反復リンクリスト

循環連鎖表は単一連鎖表の特殊なもので、単一連鎖表と異なる点は、末尾ノードがヌルアドレスを指すのではなく、連鎖の先頭ノードを指す点です。連鎖の末尾から連鎖の先頭に行くのがより便利であるという利点があり、処理するデータがリング構造の特徴を持つ場合、循環連鎖表による処理に非常に適しています。

双方向連鎖テーブル

双方向リンクテーブルは双方向をサポートしており、各ノードはその後ろのノードを指す子孫ポインタnextだけでなく、その前のノードを指す前任者ポインタprevも持っています。

双方向円形チェーンテーブル

アレイとの性能比較

長所と短所

• 利点：ダイナミックな拡張が可能で、多くのメモリを占有する必要がありません。
• 欠点：ランダムにアクセスすることはできません、あなたが要素にアクセスしたい場合は、インデックスに従ってアクセスすることはできません、あなたは唯一の対応する要素を見つけるために最初からトラバースすることができます。

一般的なヒント

• 1.ダミーノードを使う。ダミーノードとは、連鎖表の先頭の前に、先頭を指すノードを追加することです。これはダミー・ノードとして理解することができ、主にフォワード・ポインタを持たない単一リンク・テーブルの問題に使用され、削除操作でリンク・テーブルの先頭が失われないようにします。通常、削除や変更によってリンクされたテーブルの先頭が変更された場合、ダミーノードを作成することができます：

  ListNode dummy = new ListNode(0);
  dummy.next = head;
  

  これにより、HEADノードの操作は他のノードの操作と区別がつかなくなります。

• 2.ダブル・ポインタ法。連鎖したテーブルの特定の位置を見つけたり、リングがあるかどうかを判断したりするような問題には、fastとslowの2つのポインタ変数を使うことができます。

  ListNode slow = head;
  ListNode fast = head;
  

  異なる速度でチェーンテーブルをトラバースし、目標位置を見つけます。注意：テストの際には、チェーンテーブルの長さが奇数と偶数でそれぞれテストケースを選択する必要があります。

• 3.ノードの入れ替え処理質問24 ように、2つのノードの位置を入れ替える必要がある場合、隣接する2つのノードを入れ替える必要があり、これらの2つの先行ノードに対して、それらの次のポインタが影響を受け、2つのノード自体も影響を受けることになります：

  • 1) まず、2つの先行ノードの次のポインタの値を交換します。
  • 2) 次に、これら2つのノードの次のポインタの値を交換します。

  上記の処理は、これら2つのノードの相対位置や絶対位置に関係なく保持されます。

• 例: 19 リストの最後から N 番目のノードを削除 中

質問要約

基本操作

クラスの削除

• 例： 19 リストの最後から N 番目のノードを削除 中
• test case:
• テストケースです。

与えられた÷リスト：1->2->3->4->5、n = 2。

1->2->3->5へのチェーンテーブルのリードの2番目のノードを削除します。

• 解決案：.headの前に仮想ノードダミーノードを追加し、fastとslowの2つのポインタを設定します。 fastポインタの現象はnノード先に移動し、その後fastとslowは同時に移動を開始します。fast.next == Noneのとき、slowノードは.nextを指して削除する必要があるノードの前のノードを指しています。next
• コード

ジャワ

class Solution{
public static ListNode removeNthFromEnd(ListNode head, int n) {
 ListNode dummy = new ListNode(0);
 dummy.next = head;
 ListNode fast = dummy;
 ListNode slow = dummy;
 while(fast.next != null){
 	if(n <= 0)
 		slow = slow.next;
 	fast = fast.next;
 	n--;
 }
 if(slow.next != null)
 	slow.next = slow.next.next;
 return dummy.next;
 }
}

• 例1: 簡単な206の逆リンクリスト

リートコードはクラスを削除するためのトピックを含んでいます：

フリップタイプの質問

• 例1: 簡単な206の逆リンクリスト

• test case:

  Input >2->3->4->5->NULL

  Output >4->3->2->1->NULL

• テストケースです。

  Input >2->3->4->5->NULL

  Output >4->3->2->1->NULL

• 考える：これは反復と再帰の両方を使ってできますか？

• 解答：問題のフリップタイプでは、ヘッド->プレブノードをプレブヘッドにフリップする方法を知っている必要がありますすることができます、ここではまだダミーノードを使用する必要があり、ヘッドの前駆ノードとして、前にフリップでは、それはダミー->ヘッド->2->3...->NULL、NULLにフリップした後->5->...->2->ヘッド->ダミー、ダミーはテールノードに、これは一方向チェーンテーブルであるため、ヘッドは唯一のポインタを持っている、ヘッド->ヘッドへのポインタをされている、ダミーはテールノードに。>5->...->2->head->ダミー、ダミーはテールノードになります。これは単方向のチェーンテーブルなので、headはポインタを1つしか持っておらず、それはすでに次のノードを指しています。'、headがdummyを指すように、つまりdummy->headがhead->dummyになるようにすれば、最初のステップは完了です。後者の書き方には2通りあり、1つは反復的なもので、head->head.nextを処理するのと同じように、head.next->headになるように戻ってくることができます。ここで実際にはhead.next.nextの最初のステップに相当し、head.nextは、ダミーの最初のステップに相当するので、直接ダミー=ヘッド、ヘッド= nextを書くことができます;再帰的な方法は、再帰関数を作成する必要があり、ステップの最初のステップは、再帰関数に書き込まれ、常にこの再帰関数を呼び出すことができます。

• コード

  ジャワ

  /*繰り返し書く*/
  class Solution {
   public ListNode reverseList(ListNode head) {
   if (head == null || head.next == null){
   return head;
   }
   ListNode dummy = null;
   while (head != null){
   ListNode next = head.next;
   head.next = dummy;
   dummy = head;
   head = next;
   } 
   return dummy;
   }
  }
  /*再帰的記述*/
  class Solution{
   public ListNode reverseList(ListNode head) {
   return reverseListHelper(head, null);
   }
   private ListNode reverseListHelper(ListNode head, ListNode newHead) {
   if (head == null)
   return newHead;
   ListNode next = head.next;
   head.next = newHead;
   return reverseListHelper(next, head);
   }
  }
  

• 例 2: 92 逆リンクリスト媒体

• 例2：92個の逆リンクリスト媒体

• トピック: チェーンテーブルをm->nの位置で反転させます。

• code

  /* */
  class Solution{
   public ListNode reverseBetween(ListNode head, int m, int n) {
   ListNode dummyHead = new ListNode(0);
   dummyHead.next = head;
   ListNode g = dummyHead;
   ListNode p = dummyHead.next;
   int step = 0;
   while (step < m - 1) {
   g = g.next; p = p.next;
   step ++;
   }
   for (int i = 0; i < n - m; i++) {
   ListNode removed = p.next;
   p.next = p.next.next;
   removed.next = g.next;
   g.next = removed;
   }
   return dummyHead.next;
   }
  }
  /* */
  class Solution {
   private boolean stop;
   private ListNode left;
   public void recurseAndReverse(ListNode right, int m, int n) {
   if (n == 1) {
   return;
   }
   right = right.next;
   if (m > 1) {
   this.left = this.left.next;
   }
   this.recurseAndReverse(right, m - 1, n - 1);
   if (this.left == right || right.next == this.left) {
   this.stop = true; 
   }
   if (!this.stop) {
   int t = this.left.val;
   this.left.val = right.val;
   right.val = t;
   this.left = this.left.next;
   }
   }
   public ListNode reverseBetween(ListNode head, int m, int n) {
   this.left = head;
   this.stop = false;
   this.recurseAndReverse(head, m, n);
   return head;
   }
  }
  

• 複雑さ解析

• 複雑さ解析：

• 時間の複雑さ	O(N)	O(N)
  空間の複雑さ	O(1)	O(N)

  反復法：時間の複雑さはO(N)、ポインタは元のチェーンテーブル上を移動するので、空間の複雑さはO(1)

  再帰メソッド：各ノードを最大2回、通常の再帰とバックトラック再帰でトラバースする必要があるため、時間の複雑さはO(N)、最悪の場合、チェーンテーブル全体を反転する必要があり、再帰メソッドはスタックを占有するため、空間の複雑さはO(N)

  リートコードには、連鎖したテーブルを反転させるトピックが含まれています：

リンクリストの結合

• 例: 21 並べ替えられた2つのリストを簡単にマージ

• test case:

  Input: 1->2->4, 1->3->4

  Output: 1->1->2->3->4->4

• テストケースです。

  Input: 1->2->4, 1->3->4

  Output: 1->1->2->3->4->4

• 解決方法: 反復法と再帰法。反復法とは、一度に2つのノードを比較し、小さい方のノードを結果のリストに追加し、このポインタを後方に移動させる方法です。再帰法とは、一度に2つのリストの先頭を比較し、小さい方の先頭を個別に取り出し、残りの2つの部分について再帰を続ける方法です。

• コード

ジャワ

/* */
class Solution{
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode cur = head;
		while (l1 != null && l2 != null) {
			if (l1.val >= l2.val) {
				cur.next = l2;
				l2 = l2.next;
			} else {
				cur.next = l1;
				l1 = l1.next;
			}
			cur = cur.next;
		}
 
		if (l1 != null)
			cur.next = l1;
		if (l2 != null)
			cur.next = l2;
		return head.next;
	}
}
/* */
class Solution {
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 if (l1.val > l2.val) {
 ListNode tmp = l2;
 tmp.next = mergeTwoLists(l1, l2.next);
 return tmp;
 } else {
 ListNode tmp = l1;
 tmp.next = mergeTwoLists(l1.next, l2);
 return tmp;
 }
 }
}

• 例: 21 k個のソートされたリストのマージ
• トピック: k 個の順序付き連結テーブルのマージ
• 解答：パーティショニング・アルゴリズムは、リンクされたテーブルを2つずつマージし、最後に1つのリンクされたテーブルにマージします。リンクされたテーブルの平均ノード数はnで、2つのリンクされたテーブルをマージするのはO(n)、k個のリンクされたテーブルをマージするのはO(logk)、マージするのはO(nlogk)

class Solution {
 public ListNode mergeKLists(ListNode[] lists) {
 if(lists == null || lists.length == 0) return null;
 return partion(lists, 0, lists.length - 1);
 }
 private ListNode partion(ListNode[] lists, int start, int end) {
 if(start == end) {
 return lists[start];
 }
 else if(start < end) {
 int mid = (start + end) / 2;
 ListNode l1 = partion(lists, start, mid);
 ListNode l2 = partion(lists, mid + 1, end);
 return merge(l1, l2);
 }
 else {
 //not gonna happen.
 return null;
 } 
 }
 private ListNode merge(ListNode l1, ListNode l2) {
 if(l1 == null) return l2;
 if(l2 == null) return l1;
 if(l1.val < l2.val) {
 l1.next = merge(l1.next, l2);
 return l1;
 } else {
 l2.next = merge(l1, l2.next);
 return l2;
 }
 }
}

LeetCodeにはMerged Chained Tablesクラスのトピックが含まれています：

円形リンクリスト

• 例: 141 簡単なリンクリストサイクル

• 質問：1つのリンクされたテーブルにリングが存在するかどうかを判断してください。

• テストケースです。

  入力 : head = [3, 2, 0, -4], pos = 1

  出力 : true

  WHY：このシングル・リンク・テーブルにはリングがあり、最後尾のノードは2番目のノードを指しています。

• 解答：ダブルポインタ法。この問題は、ダブルポインタを使うことができます。ダブルポインタは、速いポインタと遅いポインタ、またはランナーとチェイサーとも呼ばれます。この問題では、速いポインタが2ステップ、遅いポインタが1ステップずつ進むように設定します。 速いポインタが最後まで進めば、連鎖表にはループがなく、速いポインタと遅いポインタが出会えば、連鎖表にはループがあることになります。なぜ？リングのある連鎖表を仮定すると、速いポインタと遅いポインタはリングの上に行き着きます。リングは円形の滑走路のようなもので、遅いポインタは後ろに、速いポインタは前にいますが、実際には速いポインタも遅いポインタを1周追い越そうと追いかけています。彼らはこの滑走路上にいて、速い手が遅い手に追いつく日が必ず来るのです。2人のスピードの差は1なので、リング上の距離は毎回必ず1ずつ縮まり、最後は必ず0になりますから、速いポインターが遅いポインターを飛び越える心配はありません。

• コード

ジャワ

public class Solution {
 public boolean hasCycle(ListNode head) {
 if(head==null) return false;
 ListNode slow = head;
 ListNode fast = head;
 while(fast.next!=null && fast.next.next!=null) {
 slow = slow.next;
 fast = fast.next.next;
 if(slow==fast) return true;
 }
 return false;
 }
}

• 例: 86 パーティションリスト

LeetCodeには、円形チェーンテーブルに関するトピックが含まれています：

連鎖したテーブルの分割

• 例：86 パーティション・リスト・メディア

• このアイデアは、リンクされた表と目標値が与えられた場合、元のリンクされた表のこれらの2つの部分の相対的な位置を維持しながら、目標値より小さいすべてのノードを表の前に移動し、目標値以上のノードを表の最後に移動します。

• テストケースです。

• 解決策： 二分法。左右の2つのポインタをセットし、左右または右左の状況に応じて、左、中、ターゲット比較の順にチェーンテーブル全体をトラバースします。キーは境界ケースにあり、要素が重複しています。

  • nums[mid] = nums[left]の場合、ターゲットがどこに落ちるかを判断するのは難しいので、left++を取るしかありません。

  • nums[mid] > nums[left]の場合、以下の2つのケースに分けられます。

  • nums[mid] < nums[left]の場合、これは2つのケースに分けることができ、右半分を判断するのは簡単です。

• 複雑さ解析

ジャワ

class Solution {
 public boolean search(int[] nums, int target) {
 int left = 0, right = nums.length - 1;
 
 while (left <= right) {
 int mid = (left + right) / 2;
 if (target == nums[mid]) return true;
 if (nums[mid] == nums[left]) left++;
 
 else if (nums[mid] > nums[left]) {
 if (nums[left] <= target && nums[mid] > target) right = mid - 1;
 else left = mid + 1;
 } else {
 if (nums[mid] < target && target <= nums[right]) left = mid + 1;
 else right = mid - 1;
 }
 }
 return false;
 }
}

• 例: 148 ソートリストメディアム

LeetCodeは分割とソートに関するトピックを含んでいます：

並べ替え連鎖リスト

• 例: 148 ソートリストメディアム
• test case:
• テストケースです。

Input: 4->2->1->3

Output: 1->2->3->4

• アイデア : マージソート。この問題には多くの解決策がありますが、時間複雑度がO(nlogn)であることがトピックです。この条件を満たすために、クイックソート、ヒープソート、サブサンプションソートがあり、3つの空間複雑度はO(1)、O(N)、)O(N)でした。連鎖リストの場合、マージ操作は配列のマージ操作のように一時的な配列空間を確保する必要がないので、空間複雑度はO(1)です。
• 高速ソートとサブサンプション・ソートの時間計算量はどちらもO(nlogn)であり、高速ソートはサブサンプション・ソートよりも高速であることが証明されています。
• コード

ジャワ

public class Solution {
 
 public ListNode sortList(ListNode head) {
 if (head == null || head.next == null)
 return head;
 
 // step 1.鎖でつながれたテーブルを半分に分ける
 ListNode prev = null, slow = head, fast = head;
 
 while (fast != null && fast.next != null) {
 prev = slow;
 slow = slow.next;
 fast = fast.next.next;
 }
 
 prev.next = null;
 
 // step 2.リンクリストをパートごとにソートする
 ListNode l1 = sortList(head);
 ListNode l2 = sortList(slow);
 
 // step 3. l2とl2をマージする
 return merge(l1, l2);
 }
 
 ListNode merge(ListNode l1, ListNode l2) {
 ListNode l = new ListNode(0), p = l;
 
 while (l1 != null && l2 != null) {
 if (l1.val < l2.val) {
 p.next = l1;
 l1 = l1.next;
 } else {
 p.next = l2;
 l2 = l2.next;
 }
 p = p.next;
 }
 
 if (l1 != null)
 p.next = l1;
 
 if (l2 != null)
 p.next = l2;
 
 return l.next;
 }
}

• THINK ANSWER: ソートされる要素が配列に格納されている場合、クイックソートはサブサンプションソートよりも速くなります。ひとつは、要素の読み込みが非常に速く行えること、そして配列の分割のステップがリンクリストの分割のステップよりも速いことです。第二に、マージソートはマージ段階で補助配列を必要とし、O(N)の空間を必要とします。高速ソートでは、追加のスペースを必要としません。ソートされる要素が連結表に格納されている場合、高速ソートの利点は欠点になります。その場合、マージソートの方が高速です。

LeetCode 連鎖リストのソートに関するトピックが含まれています：

概要

これらのトピックは一般的に、解決できるいくつかの対応するテクニックを持っています。

まずはセンチネルノードの導入。これが冒頭で説明したダミー・ノードです。連鎖表が空であろうとなかろうと、いつでも先頭ノードは常にこのセンチネルノードを指します。このようなセンチネルノードを持つ連鎖表をヘッド付き連鎖表とも呼びます。

次に、2ポインタ・メソッド。これは、リンクされたテーブルの中の位置を見つけたり、リンクされたテーブルがリングを持っているかどうかを判断したりするのに使われます。

3つ目は、分割によるマージです。この使い方は、k個のソート済みリンクリストをマージしたり、2つの順序なしリンクリストをソートしたりするような、リンクリストのソートに適しています。

第四に、質問に答える過程で、境界のケースをもっと考慮すべきです。

• チェーンテーブルは空です。
• チェーンテーブルのノードは1つだけです。
• 連鎖したテーブルには、次の 2 つのノードだけが含まれます。
• ヘッドノードとテールノードを扱うコードに問題はありますか？

1.

2...

help star