【LeetCode】142.リングチェーンテーブルII

2267 ワード
タイトルの説明
142.リングチェーンテーブルII
チェーンテーブルが与えられ、チェーンテーブルがループを開始した最初のノードを返します.チェーンテーブルにループがない場合はnullを返します.与えられたチェーンテーブルのループを表すために、整数posを使用してチェーンテーブルの最後にチェーンテーブルに接続された位置を表します(インデックスは0から始まります).posが-1の場合、チェーンテーブルにリングはありません.説明:指定したチェーンテーブルの変更は許可されていません.
   1：
  ：head = [3,2,0,-4], pos = 1
  ：tail connects to node index 1
  ：       ，           。

   2：
  ：head = [1,2], pos = 0
  ：tail connects to node index 0
  ：       ，           。

テーマ解析
方法1:ハッシュテーブル
問題を解く構想.
まず考えられる方法は,チェーンテーブルを遍歴し,遍歴したチェーンテーブルNodeノードをハッシュテーブルに格納し,チェーンテーブルにループがあれば最初に出現した重複するNodeノードを返すことである.
コードの例
Java: 
/* 
* Definition for singly-linked list.
*/
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode detectCycle(ListNode head) {
    Set visited = new HashSet();
    ListNode curr = head;
    while (curr != null) {
        if (visited.contains(curr)) {
            return curr;
        }
        visited.add(curr);
        curr = curr.next;
    }

    return null;
}

複雑度分析
時間複雑度:O(n)
空間複雑度:O(n)で、余分な空間を介してノードを格納する
方法2:ダブルポインタ
問題を解く構想.
前の問題のリングチェーンテーブルでは、チェーンテーブルにリングがある場合、スナップポインタがノードで出会うと述べています.
このとき、チェーンヘッダノードからループ開始点までの距離はxであり、ループ開始点から高速ポインタがノードに出会うまでの距離はyであり、その後、ノードはzの距離を歩き続けてループ開始点に戻る.
速いポインタの速度は遅いポインタの2倍であるため、速いポインタが遅いポインタに追いつくと必ず遅いポインタより1周多く歩かなければならない.このとき、スローポインタが走行する経路s=x+y、クイックポインタが走行する経路f=x+y+z+y、およびf=2 sは、すべてx=zを得ることができ、すなわち、ヘッダノードからループ開始点までの距離は、ポインタがノードからループ開始点までの距離に等しい.したがって、スナップポインタが出会うと、1つのポインタがヘッダノードに戻り、2つのポインタが再び出会うまで等しい速度でループを継続することを指定します.
コードの例
Java: 
/* 
* Definition for singly-linked list.
*/
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (true) {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}

複雑度分析
時間複雑度:O(n)
空間複雑度:O(1)
Linux忘れrootパスワード処理
単一チェーンテーブルの分割