1.単一のリンクされたテーブルのカウントダウンで指定されたノードを操作する必要があります。
1.1 問題解決のアイデアとコードテンプレート
このタイプのアルゴリズム問題の核となるキーは、問題で与えられた特定のノードの位置を特定する必要があることで、この指定されたノードの位置さえ見つかれば、残りの問題はかなりよく解けます。以下にLeetCodeのアルゴリズム問題をいくつか挙げますので、一緒に感じてください。
このようなトピックを行うには、アイデアは基本的に似ている、あなたはテンプレートのうち、同様のトピックのこの種を要約することができます：この種の問題は、多くの場合、問題を解決するために、高速および低速ポインタを使用していますあなたが操作したいノードの位置を見つけるために、対応する位置を見つけるために、対応する操作のタイトルによると、それに実施することができます。ここで私は、単純に動く絵を行うには、まず、高速ポインタがkのステップを歩くようにし、その後、一緒に後方に移動するために、高速および低速ポインタを聞かせて、最後のチェーンテーブルノードを見つけました。
そのテンプレートコードは以下の通りです：
public static ListNode method(ListNode head, int k) {
//高速ポインタ、まず、kのステップを取ろう。
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
//その後、高速ポインタと低速ポインタが一緒に、高速ポインタがチェーンテーブルの最後に、低速ポインタが最後からK個のノードを指すとき
ListNode temp = head;
//あなたが探しているk番目の末尾ノードの前のノード。k番目のノードを操作したい場合、一般的にはk番目のノードの前任者のノードを見つける必要があるからだ。
//上記の2番目のアルゴリズムの質問のように、チェーンテーブルのK番目のノードを削除するには、preNodeを使用する必要がある
ListNode preNode = null;
while (fast != null ) {
preNode = temp;
temp = temp.next;
fast = fast.next;
}
return temp;
}
最初のアルゴリズムの問題は、上記のテンプレートコードを使用して解くことができます。
番目のノードの削除を必要とする2番目のアルゴリズム問題は、上記のコード・テンプレートを使用してまだ見つかりますが、ここでは、最後からk番目のノードを操作するために、最初にこのノードのノードを見つけることを確認してください。,
3つ目のアルゴリズム問題はLeetcodeの中程度の難易度の問題で、アイデアと前の2つのアルゴリズム問題はほぼ同じアイデアです。問題は、リンクされた表が与えられたとき、表を回転させ、各ノードを1つ右に移動させます。
この問題には、回転の長さがチェーンテーブルの長さを超えてはいけないという制限はありませんから、回転がチェーンテーブルの長さを超える可能性はあります：
- リンクされたテーブルの長さの計算
- 回転の長さを決定するために、ここではk%の長さを用います；
- 上記の方法で回転させるノードの位置を決めます。
- 望む結果を得るために。
その完全なコードは以下の通り：
public ListNode rotateRight(ListNode head, int k) {
if(head ==null||head.next ==null){
return head;
}
//まず、チェーンテーブルの長さを取得する。
int nodeLength = 0;
ListNode d = head;
while (d != null) {
nodeLength++;
d = d.next;
}
//長さを取得した後、移動する必要があるノードの数を計算する。
int remaind =k % nodeLength ;
//midが0に等しい場合は、移動しないのと同じである。
if (mid == 0) {
return head;
}
d = head;
//ここでは、上記の高速ポインタと低速ポインタは、まず高速ポインタがremaind行くことができる。
for (int i = 0; i < remaind; i++) {
d = d.next;
}
ListNode temp = head;
//遅いポインタが指す前のノードを記録する
ListNode prev = null;
//高速ポインタが指す前のノードを記録する
ListNode tailPrev = null;
while (d != null) {
prev = temp;
tailPrev = d;
temp = temp.next;
d = d.next;
}
prev.next = null;
tailPrev.next = head;
return temp;
}
必要性のこのタイプに加えて、実際には、また、指定されたノードの場所を見つけるために必要性がある、このノードは、同様のトピックはまた、高速と低速のポインタを使用する必要があるように、中間ノードに、より具体的である解決することができますので、高速ポインタは、2つのステップを取るたびに低速ポインタは、ステップを取るたびに、チェーンテーブルの端に高速ポインタは、チェーンテーブルの真ん中のノードを指すように低速ポインタをさせるようにします。
public static ListNode findMidNode(ListNode head) {
ListNode fastNode = head;
ListNode slowNode = head;
ListNode prev = null;
while (fastNode != null && fastNode.next != null) {
prev = slowNode;
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
return slowNode;
}
練習トピック
上記を読んだ後、この問題（原題はこちら：連鎖したリストの並べ替え）で練習してください。
L0→L1→...→L**n-1→Lnという1つのリンクされた表Lがある場合、単純にノードの中の値を変えるだけではだめで、実際にノードを入れ替える必要があります。例1: リンクされたテーブル1->2->3->4がある場合、1->4->2->3に並べ替えます。 例2: リンクされたテーブル1->2->3->4->5がある場合、1->5->2->4->3に並べ替えます。
チェーンテーブルを反転させるアイデアは、実際には2種類あり、1つは元のチェーンテーブル上にあり、もう1つは、このデータ構造のスタックを使用することであり、O(1)の空間複雑度の場合、あなたは追加のデータ構造を使用することはできません、あなたは唯一の反転のためにチェーンテーブルを操作するポインタを使用することができます。
public static ListNode reverseList(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
もう一つの方法はスタックを使うことで、これは書くのが簡単で、ここでは自分で書くことができます。以下は、チェーンテーブルを並べ替えるための完全なコードです。
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
//チェーンテーブルの真ん中のノードの位置を見つける
ListNode fast = head;
ListNode slow = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
//ここでは、元のチェーンテーブルの頭を変更し、頭はチェーンテーブルの前半である
prev.next = null;
//slow それは連鎖表の後半で、ここでは連鎖表の後半が逆になっている。ここではスタックを使うことができる。
ListNode listNode = reverseList(slow);
//ここでは、1つに2つの連鎖表になり、ここで行うには、新しい連鎖表を作成することができ、また、頭の上に直接操作することができる。しかし、私は効果のパフォーマンスは悪くないテストした。
//頭の上の操作は少し複雑になる可能性があり、いくつかのポインタを使用して行う必要があり、未熟な直接新しいチェーンテーブルを作成することができますので、ポインタは、自分が迷子になりやすい周りを指す。
//スタックの使用も達成することができ、ここではそれを自分で試すことができる。
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while(head != null && listNode != null){
curr.next = head;
head = head.next;
curr.next.next = listNode;
listNode = listNode.next;
curr = curr.next.next;
}
//ここでは、チェーンテーブルの後半が空であることを決定するために注意を払う必要がある、あなたはチェーンテーブルがノードの奇数または偶数であることを知ることができる。
//もしノードの数が奇数なら、連鎖表の後半は前半よりノードが一つ多くなる、真ん中のノードは後半に数えられるからだ。
if(listNode != null){
curr.next = listNode;
}
head = dummy.next;
}
public static ListNode reverseList(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
2.回文とリングリストのアルゴリズム
回文と循環連鎖表の話題はまだ比較的簡単です。回文の判定は前半と同じで、速いポインタと遅いポインタを使って中点の位置を求め、後半と前半を比べて逆順になっているかどうかを調べます。ここでは、環状連鎖表の解法を中心に説明します。
2.1 問題解決のアイデアとコードテンプレート
最初のアイデアは、ハッシュ・テーブルを使ってチェーン・テーブル全体をトラバースするというものです。
public static boolean hasCycle2(ListNode head) {
HashSet set = new HashSet();
while (head != null) {
if (set.contains(head)) {
return true;
} else {
set.add(head);
}
head = head.next;
}
return false;
}
ハッシュ・テーブルを使ったこの解決法の時間の複雑さはO(n)で、空間の複雑さもO(n)です。この方法は最も単純で考えやすいものです。
つ目のアイデアは、高速ポインタと低速ポインタを使い、高速ポインタの速度が低速ポインタの速度の2倍になるようにすることで、連鎖表全体を縦断するためには、1つの連鎖表にリングがある場合、2つのポインタはあるノードで出会う必要があります。コードは以下の通り：
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
if (head == null || head.next == null) {
return false;
}
return false;
}
リング状リストの高度な問題： リング状リストの最初のノードを返すか、リングがない場合は Null を返します。
1つのリンクされたテーブルにリングがある場合、2つのポインタは必ずリング上のいずれかのノードで出会います。2つのポインタが出会った時、遅いポインタはlen + s1の長さを移動したことになり、速いポインタはlen + n(s1 + s2) + s1の長さを移動したことになります。2(len+S1) = len + n(S1+S2)+S1高速ポインタは低速ポインタの2倍の速さなので、同じ時間で移動した長さは等しくなければなりません。この式は定数です。変数nを無視するときは、n = 1を聞かせて、式はlen = s2になります。その後、2つのポインタがそれぞれ、会うときであり、その後、AノードとCノードから同時に2つのポインタを聞かせて、ノードを移動するたびに、再び会う時間は、環状チェーンテーブルの入口ノードです。コードは次のとおりです：
public ListNode hasCycle(ListNode head) {
ListNode slow = head,fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) return null;
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
3.リンクリストの並べ替えとマージ
アルゴリズムのタイトル
3.1 問題解決のアイデア
最初のアルゴリズムの質問は、連鎖表の並べ替えと通常のデータの並べ替えは同じアイデアですが、連鎖表は、ランダムに連鎖表のノードにアクセスすることはできませんので、唯一の連鎖表全体をトラバースして、ここでは、連鎖表のサブサンプションソートのメソッドを使用することができます、私たちはすでにサブサンプションソートに精通していると信じて、ここで直接コードに。
連鎖表のマージソートを行うには、まず連鎖表の中点を見つけて2つの部分に分割し、その2つの部分をソートします。そして連鎖表の2つの部分それぞれについて、最後まで前述の操作を繰り返します。
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
return merge(left, right) ;
}
//左と右の部分をマージする
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode temp1 = l1, temp2 = l2;
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (temp1 != null && temp2 != null) {
if (temp1.val > temp2.val) {
dummy.next = temp2;
temp2 = temp2.next;
} else {
dummy.next = temp1;
temp1 = temp1.next;
}
dummy = dummy.next;
}
dummy.next = temp1 != null ? temp1 : temp2;
return prev.next;
}
実際、2つの順序付き連鎖表をマージすることは、最初のアルゴリズム問題の一部であり、2つの順序付き連鎖表をマージするコードは、最初のアルゴリズム問題の後の部分で直接使用することができます。この方法は2つの順序付きリストのマージにしか使えないことに注意してください。
では、3番目のアルゴリズム問題である、K個の順序付き連鎖表をマージするようなことは、どのようにすればよいのでしょうか？実はこれにはいくつかの方法があります：
1Javaの優先順位キューPriorityQueueの使用は、PriorityQueueバイナリヒープの基礎となる使用を達成するために、最小の要素は、常にヒープの先頭になりますので、複数の順序付けられたチェーンテーブルをマージすることができます。ただし、複数のリンクリストを行うには順序付けされていることに注意することが重要です、複数の順序のないリンクリストをマージするときは、そうすることはできません。
2.まだに関係なく、いくつかの連鎖表の合併の2番目の質問のアイデアを使用して継続することができます、あなたはそれらを2つずつマージすることができ、最終的に連鎖表に集計され、このソリューションに関係なく、連鎖表は、順序または順序なしの、この方法で操作することができます。
- プライオリティキュー
public static ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((v1,v2)->v1.val - v2.val);
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummyHead = new ListNode(-1);
ListNode tail = dummyHead;
while (!pq.isEmpty()) {
ListNode minNode = pq.poll();
tail.next = minNode;
tail = minNode;
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummyHead.next;
}
- 2つずつマージ
public static ListNode mergeKLists2(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return helper(lists, 0, lists.length - 1);
}
private static ListNode helper(ListNode[] lists, int begin, int end) {
if(begin==end) {
return lists[begin];
}
int mid = begin+(end-begin)/2;
ListNode left = helper(lists,begin,mid);
ListNode right = helper(lists,mid+1,end);
return merge(left,right);
}
//2つの順序付きリンクリストをマージする
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode temp1 = l1, temp2 = l2;
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (temp1 != null && temp2 != null) {
if (temp1.val > temp2.val) {
dummy.next = temp2;
temp2 = temp2.next;
} else {
dummy.next = temp1;
temp1 = temp1.next;
}
dummy = dummy.next;
}
dummy.next = temp1 != null ? temp1 : temp2;
return prev.next;
}
4.チェーンテーブル交換タイプのトピック
このタイプのトピックに適用できる決まったテンプレートはなく、必要なのはこのタイプのトピックを解く感覚をつかむことだけです。適用できる固定テンプレートはありませんが、それでも描けるキーポイントはあります。ステップ1：いつ2つのノードを交換する必要があるかを判断する必要があります。上の最初のアルゴリズム問題を例にとると、交換が必要なノードは3番目から5番目のノードです。ステップ2：次に、交換が必要なノードの先行ノードと後行ノードを見つけます。こうすることで、ノードをうまく移動させることができます。ステップ3: このステップでは、後続のループ動作を満たすことができるポインタの移動方法を決定します。
ステップ1：質問に従って，交換が必要なノードの位置を求めます． ここでは，kからnの間にあるノードを交換する必要があり，それ以外のノードは移動する必要がないと与えられています．したがって，ここでは，トラバースされたチェーンテーブルの長さがk-n個の間のノードかどうかを判断する必要があります．
ステップ2：交換するノードの前任ノードと後任ノードを見つけます。ここでは、チェーンテーブルの3から5までのノードをトラバースしています。交換するノードの位置が特定できたので、交換するノードの前任ノードと後任ノードを見つけ、2つのポインタpreNodeとnextNodeを使って前任ノードと後任ノードを保存します。そして、チェーン・テーブルを必要な位置に入れ替えます。
パートIII：ノードのスワップが完了したら、それに応じて使用する必要があるポインタも移動する必要があります。
全コードは以下の通り：
public static ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
int length = 0;
ListNode temp;
while (head.next != null) {
length++;
//ノードを交換する必要がある条件を見つける
if (length >= m && length < n) {
//ヘッドの後継ノードを保存する
temp = head.next;
//head.next 後継ノードが後継ノードを指す
head.next = temp.next;
temp.next = prev.next;
prev.next = temp;
} else {
if (length < m) {
prev = prev.next;
}
head = head.next;
}
}
return dummy.next;
}
2つ目のアルゴリズムに関する質問、2と2はチェーンテーブルを交換する、このトピックは実際には非常に簡単です。
3つ目のアルゴリズム問題は、LeetCodeでは難しいアルゴリズム問題ですが、実は問題の難しさは置いておいて、少し分解してみると、実はとても簡単であることがわかります。問題の要求はK個のリンクリストの集合をフリップすることで、Kはリンクリストの長さより小さいです。実際には、K個の連鎖表をフリップすることも、1つの連鎖表をフリップすることも変わりませんが、K個の連鎖表をフリップのグループに分割し、連鎖表の後の各フリップの後につなぎ合わせることができるというだけです。
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = start;
}
return dummy.next;
}
public static ListNode reverse(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
ここでは、すべての種類を一つずつ記載されていない、アルゴリズムのトピックのほとんどはほとんど同じですが、私はここで彼らは大まかに次のように分割されます：チェーンテーブルの指定されたノードの操作、チェーンテーブルのソート、円形チェーンテーブル、チェーンテーブルノード交換、チェーンテーブルを検索して削除するには、チェーンテーブル、逆とアイデアの他のタイプのチェーンテーブルが同じですが、まだもっと練習する必要があり、アイデアがあり、2つの完全に異なるものから書き出すことができます。
最後に
ここでは、すべての種類を一つずつ記載されていない、アルゴリズムのトピックのほとんどはほとんど同じですが、私はここで彼らは大まかに次のように分割されます：チェーンテーブルの指定されたノードの操作、チェーンテーブルのソート、円形チェーンテーブル、チェーンテーブルノード交換、チェーンテーブルを検索して削除するには、チェーンテーブル、逆とアイデアの他のタイプのチェーンテーブルが同じですが、まだもっと練習する必要があり、アイデアがあり、2つの完全に異なるものから書き出すことができます。
