チェーンテーブルの一般的なテクニック:高速ポインタ
21538 ワード
チェーンテーブルを処理するとき、previousとcurrent、すなわちcurrentがpreviousより前のノードを通過する2つのポインタをよく使用します.このブログで私が紹介する「急行ポインタ」のポインタテクニックも似ています.
2つのポインタ、1つのslowRunner、1つのfastRunner;fastRunnerの「速い」ことは、slowRunnerよりも先頭に立っているN個のノードに現れるか、slowRunnerが1個のノードを前進するたびにfastRunnerが2個のノードを前進するように「速く走る」ことに現れる.具体的な設計は実際の問題に基づいている.以下にいくつかの例を挙げて、みんながもっとよく理解することを助けます.
1単一チェーンテーブルの最後からk番目のノードを特定する(k=1は最後のノードを指す)
チェーンテーブルの問題は、問題を一度に解決できるかどうかを最初に考えなければならないので、何度も繰り返しているアルゴリズムは紹介しません.ここでは「快行ポインタ」の解法を直接紹介します. slowRunnerは1ノードずつ前進する. fastRunnerはslowRunnerよりk-1ノード先頭に立っている.1ノードずつ進む fastRunnerが最後のノードに遍歴するとき、slowRunnerは を求める.
インプリメンテーション
テスト
しゅつりょく
2チェーンテーブルにループがあるかどうかを検出します(余分なスペースは許可されません)
アルゴリズム: slowRunnerは1ノード を一度に進む. fastRunnerは一度に2つのノード を進む.リングが存在する場合fastRunnerとslowRunnerは に出会う.
3ループの開始ノードを見つけます(余分なスペースは許可されません)
まず、fastRunnerはslowRunnerよりも速く、リングがなければ出会うことはできないが、彼らが出会ったノードにはどんな特性があるのだろうか.ループの開始ノードloopBeginの前にk個のノードのチェーンテーブルであると仮定すると、slowRunnerがloopBeginに到達すると、fastRunnerはすでに2*k個のノードを歩き、slowRunnerよりk個のノードを多く歩いた. リングにLoopSize個のノードが含まれているとすると、このときfastRunnerの位置はk%LoopSizeになる. チェーンの方向に沿って、その後、単位時間が1つも経たないうちにfastRunnerはslowRunnerに1つのノードに近づくが、両者の間の「距離」は当然LoopSize-k%LoopSizeであるため、(LoopSize-k%LoopSize)単位時間後に2つのノードが出会って、ノードはcollionNodeである. slowRunnerからloopBeginで解析を開始したのでcollionNodeからさらに(k%LoopSize)個のノードを歩いてloopBeginに戻りました.リングはこんなに面白いです. collisionNodeは簡単に入手でき,チェーンテーブルの先頭ノードheadは既知であり,kもLoopSizeも解析のための仮定値であり,まだ知られていない.だから、collitionNodeとheadを見つめて、loopBeginをどう求めるか考えなければなりません. headからloopBeginまでの距離はk、collionNodeからloopBeginまでの距離は(k%LoopSize)、わあ!解くことができます! collionNodeを見つけた後、1つのポインタからheadの後ろを遍歴し、1つのポインタがcollionNodeの後ろからループを中継し、彼らはloopBeginで出会うだろう.
4完全なコード
しゅつりょく
2つのポインタ、1つのslowRunner、1つのfastRunner;fastRunnerの「速い」ことは、slowRunnerよりも先頭に立っているN個のノードに現れるか、slowRunnerが1個のノードを前進するたびにfastRunnerが2個のノードを前進するように「速く走る」ことに現れる.具体的な設計は実際の問題に基づいている.以下にいくつかの例を挙げて、みんながもっとよく理解することを助けます.
1単一チェーンテーブルの最後からk番目のノードを特定する(k=1は最後のノードを指す)
チェーンテーブルの問題は、問題を一度に解決できるかどうかを最初に考えなければならないので、何度も繰り返しているアルゴリズムは紹介しません.ここでは「快行ポインタ」の解法を直接紹介します.
インプリメンテーション
public MyListNode nth2End(MyListNode list,int k) {
// slowRunner fastRunner
MyListNode slowRunner = list;
MyListNode fastRunner = slowRunner;
for(int i=0; i<k;i++){
fastRunner = fastRunner.next;
if(fastRunner == null){
return null;
}
}
//
while(fastRunner != null){
fastRunner = fastRunner.next;
slowRunner = slowRunner.next;
}
return slowRunner;
}テスト
package MyList;
import java.util.Random;
public class MyListTest {
public static void main(String[] args) {
MyListTest listTest = new MyListTest();
MyListNode list = listTest.buildList(15);
listTest.display(list);
int k = 6;
MyListNode node = listTest.nth2End(list, k);
System.out.printf("The %d-th node to the end is: %d",k,node.val);
}
public MyListNode nth2End(MyListNode list,int k) {
// slowRunner fastRunner
MyListNode slowRunner = list;
MyListNode fastRunner = slowRunner;
for(int i=0; i<k;i++){
fastRunner = fastRunner.next;
if(fastRunner == null){
return null;
}
}
//
while(fastRunner != null){
fastRunner = fastRunner.next;
slowRunner = slowRunner.next;
}
return slowRunner;
}
/** * num ， */
public MyListNode buildList(int num) {
if (num == 0) {
return null;
}
MyListNode header = new MyListNode();
Random random = new Random();
int val;
MyListNode p = header;
for (int i = 0; i < num; i++) {
val = random.nextInt(100);
p.next = new MyListNode(val);
p = p.next;
}
return header.next;
}
/** * * */
public void display(MyListNode list) {
System.out.println("***** Output the list: *****");
MyListNode p = list;
int count = 0;
while (p != null) {
System.out.printf("%-5d", p.val);
p = p.next;
count++;
if (count == 5) {
System.out.println();
count = 0;
}
}
}
}しゅつりょく
***** Output the list: *****
89 65 1 1 63
67 11 90 13 31
59 80 49 22 52
The 6-th node to the end is: 312チェーンテーブルにループがあるかどうかを検出します(余分なスペースは許可されません)
アルゴリズム:
public boolean hasLoop(MyListNode head) {
MyListNode slowRunner = head;
MyListNode fastRunner = slowRunner;
while (fastRunner != null) {
// slowRunner 1
slowRunner = slowRunner.next;
// fastRunner 2
// ， ， false
fastRunner = fastRunner.next;
if(fastRunner != null){
fastRunner = fastRunner.next;
}
else {
return false;
}
// slowRunner fastRunner
if(slowRunner.equals(fastRunner)){
return true;
}
}
return false;
}***** Output the list: *****
58 80 78 6 38
94 52 11 94 68
28 86 56 23 87
The 6-th node to the end is: 68
false
true3ループの開始ノードを見つけます(余分なスペースは許可されません)
まず、fastRunnerはslowRunnerよりも速く、リングがなければ出会うことはできないが、彼らが出会ったノードにはどんな特性があるのだろうか.
public MyListNode getLoopBegin(MyListNode head) {
MyListNode slowRunner = head;
MyListNode fastRunner = slowRunner;
while (fastRunner != null) {
// slowRunner 1
slowRunner = slowRunner.next;
// fastRunner 2
// ， ， false
fastRunner = fastRunner.next;
if (fastRunner != null) {
fastRunner = fastRunner.next;
} else {
System.err.println("The list doesn't have loop!");
return null;
}
// slowRunner fastRunner
if (slowRunner.equals(fastRunner)) {
System.out.println("The collisionNode is: " + slowRunner.val);
MyListNode fromHead = head;
while (!fromHead.equals(slowRunner)) {
fromHead = fromHead.next;
slowRunner = slowRunner.next;
}
return fromHead;
}
}
return null;
}4完全なコード
package MyList;
import java.util.HashMap;
import java.util.Random;
public class MyListTest {
public static void main(String[] args) {
MyListTest listTest = new MyListTest();
MyListNode head, end;
//
HashMap<String, MyListNode> list = listTest.buildList(15);
//
head = list.get("head");
end = list.get("end");
//
listTest.display(head);
int k = 6;
// 6
MyListNode node = listTest.nth2End(head, k);
System.out.printf("The %d-th node to the end is: %d
", k, node.val);
//
boolean ret1 = listTest.hasLoop(head);
System.out.println("
" + ret1);
// ,
end.next = node;
boolean ret2 = listTest.hasLoop(head);
System.out.println("
" + ret2);
// ， 6
MyListNode loopBegin = listTest.getLoopBegin(head);
System.out.println("The loopBegin is: " + loopBegin.val);
}
/** * */
public MyListNode getLoopBegin(MyListNode head) {
MyListNode slowRunner = head;
MyListNode fastRunner = slowRunner;
while (fastRunner != null) {
// slowRunner 1
slowRunner = slowRunner.next;
// fastRunner 2
// ， ， false
fastRunner = fastRunner.next;
if (fastRunner != null) {
fastRunner = fastRunner.next;
} else {
System.err.println("The list doesn't have loop!");
return null;
}
// slowRunner fastRunner
if (slowRunner.equals(fastRunner)) {
System.out.println("The collisionNode is: " + slowRunner.val);
MyListNode fromHead = head;
while (!fromHead.equals(slowRunner)) {
fromHead = fromHead.next;
slowRunner = slowRunner.next;
}
return fromHead;
}
}
return null;
}
public boolean hasLoop(MyListNode head) {
MyListNode slowRunner = head;
MyListNode fastRunner = slowRunner;
while (fastRunner != null) {
// slowRunner 1
slowRunner = slowRunner.next;
// fastRunner 2
// ， ， false
fastRunner = fastRunner.next;
if (fastRunner != null) {
fastRunner = fastRunner.next;
} else {
return false;
}
// slowRunner fastRunner
if (slowRunner.equals(fastRunner)) {
return true;
}
}
return false;
}
public MyListNode nth2End(MyListNode head, int k) {
// slowRunner fastRunner
MyListNode slowRunner = head;
MyListNode fastRunner = slowRunner;
for (int i = 0; i < k; i++) {
fastRunner = fastRunner.next;
if (fastRunner == null) {
return null;
}
}
//
while (fastRunner != null) {
fastRunner = fastRunner.next;
slowRunner = slowRunner.next;
}
return slowRunner;
}
/** * num ， */
public HashMap<String, MyListNode> buildList(int num) {
if (num < 1) {
return null;
}
MyListNode header = new MyListNode();
Random random = new Random();
int val;
MyListNode p = header;
for (int i = 0; i < num; i++) {
val = random.nextInt(100);
p.next = new MyListNode(val);
p = p.next;
}
HashMap<String, MyListNode> hashMap = new HashMap<>();
hashMap.put("head", header.next);
hashMap.put("end", p);
return hashMap;
}
/** * */
public void display(MyListNode list) {
System.out.println("***** Output the list: *****");
MyListNode p = list;
int count = 0;
while (p != null) {
System.out.printf("%-5d", p.val);
p = p.next;
count++;
if (count == 5) {
System.out.println();
count = 0;
}
}
}
}しゅつりょく
***** Output the list: *****
95 12 36 3 10
99 8 88 79 28
6 28 53 45 5
The 6-th node to the end is: 28
false
true
The collisionNode is: 53
The loopBegin is: 28