チェーンテーブル:クイックスローポインタ

本カタログ
1概要
2チェーンテーブル中点
3ループの有無を判断する
4リング入口の決定
5交差するか否かを判断する
6関連記事
 

1概要

速遅指針法はチェーンテーブルアルゴリズムでよく用いられる方法であり、2つのステップ長の異なる移動ポインタによって、いくつかのチェーンテーブルの問題を解決するのに役立つ.
通常、スローポインタは1つのノードを移動するたびに、速いポインタは2つのノードを移動するため、両者のパスには2倍の数学的関係(偶数ノードの場合)がある.
 

2チェーンテーブル中点

高速ポインタにより,チェーンテーブル中間ノードを決定でき,二分ルックアップなどのアルゴリズムに利用できる.

// head     ，head.next         。
ListNode slowNode = head, fastNode = head;
while (fastNode != null && fastNode.next != null) {
  slowNode = slowNode.next;
  fastNode = fastNode.next.next;
}
/*
 *     ，     ：
 *     ：fastNode null，slowNode     ；
 *     ：fastNode.next null，slowNode     （         ）。
 */

 

3ループの有無を判断する

(1)ループなし:スナップポインタが次のノードがないことをチェックした場合、チェーンテーブルにループがないことを示します.
チェーンテーブルにリングが存在しない場合、高速ポインタは最終的にチェーンテーブルの末尾に優先的に到達します.
(2)ループがある:速いポインタが遅いポインタと出会った(同じノードを指す)場合、チェーンテーブルにループがあることを説明する.
チェーンテーブルにリングが存在する場合、速いポインタは最終的に1つのリングに入り、無限のサイクルで移動し、遅いポインタも最終的にこのリングに入る.
速いポインタは遅いポインタよりも1つのノードを移動するたびに多くなるため、ループでは速いポインタが遅いポインタを追いかけ、最終的にはあるノードで「追いつく(出会う)」ことになります.

public boolean existLoop(ListNode head) {
  ListNode slowNode = head, fastNode = head;
  while (fastNode != null && fastNode.next != null) {
    slowNode = slowNode.next;
    fastNode = fastNode.next.next;
    if (slowNode == fastNode) {
      return true;
    }
  }
  return false;
}

 

4リング入口の決定

チェーンテーブルにリングが存在すると仮定すると、リングの入口位置を見つけるにはどうすればいいですか?
3でループの有無を判断すると,スローポインタは必ずループのあるノードで出会うが,出会った場合,次のような関係がある.

は、リング入口に到達するまでの距離をL(L≧0)、リング長(周長)をP(P≧2)、出会い位置距離をリング入口長さS(0≦S≦P)とする.

スローポインタ経路長=L+S(出会った場合、リング入口で出会わなければスローポインタは必ず1つのリングを満たさない)

.

クイックポインタパス長=L+n*P+S(出会ったときに既にn個のループがいっぱい)

は、L+S=n*Pであり、L=n*P−S

である.
現在の出会い位置距離リング入口はSであり、この位置からL距離を移動すると、リングの入口位置にちょうど止まる数学的関係は以下の通りである.

S + L = S + n * P - S = n * P

したがって、スナップポインタが初めて出会うと、2つの新しいポインタp 1,p 2が起動し、それぞれヘッドノードと出会いノードから移動し、毎回1ステップずつ移動し、2つのポインタが出会うと、出会いノードはリングの入口ノードであり、以下のことを検証する.

p 1 Lステップを移動した後、リングの入口位置にある.

p 2はLステップを移動した後もリングの入口位置にある.

そのため、2つのポインタが初めて出会ったのは必ずリング入口の位置にあります.

public ListNode findLoopBeginNode(ListNode head) {

  ListNode slowNode = head, fastNode = head;

  do {
    slowNode = slowNode.next;
    fastNode = fastNode.next.next;
  } while (slowNode != fastNode);

  ListNode p1 = head, p2 = fastNode;
  while (p1 != p2) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}

 

5交差するか否かを判断する

(1)方法一:
2つのチェーンテーブルをそれぞれ遍歴し、2つのチェーンテーブルの長さと末端ノードを記録する.
エンドノードが同じであれば交差があることを示し、エンドノードが異なると交差は存在しない.
交差がある場合、長鎖表ポインタは長さ差ステップ数(この場合、残りの鎖表ノード数は同じ)を先に移動し、その後、2つの鎖表ポインタが一緒に移動し、初めて出会ったノードが交差ノードとなる.

public ListNode findCrossNode(ListNode head1, ListNode head2) {
  
  ListNode node1 = head1, node2 = head2;
  int count1 = 0, count2 = 0;
  
  while (node1.next != null) {
    node1 = node1.next;
    count1++;
  }
  while (node2.next != null) {
    node2 = node2.next;
    count2++;
  }
  if (node1 != node2) {
    return null;  //    
  }

  node1 = head1;
  node2 = head2;
  while (count1 != count2) {
    if (count1 > count2) {
      node1 = node1.next;
      count1--;
    } else {
      node2 = node2.next;
      count2--;
    }
  }
  while (node1 != node2) {
    node1 = node1.next;
    node2 = node2.next;
  }
  return node1;  //    
}

 
(2)方法2:(構想のみを提供し,コードを省略する)
1つのチェーンテーブルの先頭と末尾を接続し、3つのループの有無を判断することによって、別のチェーンテーブルにループがあるか否かを判断する.
リングが存在する場合、交差点が存在し、リングが存在しない場合、交差点は存在しない.
ループが存在する場合、交差点の位置は、4つのループ入口法によって決定される.
 

6関連記事

『全配列(Java)』
『ビット演算:減算と符号補完』
『異或(^)の性質と応用』
『図解:常用ソートアルゴリズム(バブル、選択、挿入、ヒル、高速、集計、スタック)』
「遡及アルゴリズム」
『ダイナミックプランニング:卵が落ちる』
「動的計画:単語分割」
『ステータスマシン:一度しか現れない数字II』
『最小ヒープ:TopK問題』