一方向チェーンテーブルにループとルックアップループのエントリがあるかどうかを判断する

スナップポインタ

アルゴリズムの説明

2つのポインタslow,fastを定義します.slowポインタは一度に1つのノードを歩き、fastポインタは一度に2つのノードを歩きます.チェーンテーブルにリングがある場合、スローポインタは必ずまたいつかファストポインタ(slow==fast)を追いかけます.ループがない場合、スナップポインタは最初にNULLに移動します.

インプリメンテーション

ノードの定義は次のとおりです.

class Node {
    public Node next;
    public Object data;

    public static int sequence = 0;
}

アルゴリズム:

/** *      * @param head * @return */
    public static boolean checkCircle(Node head) {
        Node fast = null;
        Node slow = null;

        fast = head;
        slow = head;
        while (true) {
            //        
            if (null != slow.next) {
                slow = slow.next;
            } else {
                return false;
            }

            //        
            if (null != fast.next && null != fast.next.next) {
                fast = fast.next.next;
            } else {
                return false;
            }

            //       
            if (slow == fast) {
                return true;
            }
        }
    }

ステップチェック

アルゴリズムの説明

上のアルゴリズムはチェーンテーブルにリングがあるかどうかを判断するしかありませんが、リングの入り口を見つけたい場合はどうすればいいですか?
2つのポインタp,qを定義します.pは1つのノード(すなわちステップ)を歩くたびに、qは最初から後ろに進み、qがNULLまたはpまで歩き、qが同じノードまで歩いたが歩いたステップ数が異なるまで歩く.このときqのステップ数は,ループ入口がノード内にある位置である.NULLに移動すると、チェーンテーブルにループが存在しないことを示します.
なぜp,qは同じノードに着いたがステップ数が等しくない場合にリングがあることを説明するのか.p,qステップ数が同じであれば,それらが通過したノードが同じであることを示し,p,qステップ数が異なると,pはループから一周してループの入口に戻ったことを示し,このときqがそのノードに到達したときにまだループを通過していないため,ステップ数が等しくなく,このときqのステップ数がループの入口である.

インプリメンテーション

/** *        * @param head * @return        ， 0  。      -1 */
    public static int findCircleEntry(Node head) {
        Node p = head; //       
        Node q = head;

        int pSteps = 0;
        int qSteps = 0;
        while (null != q.next) {
            q = q.next;
            ++qSteps;

            // p     
            while (null != p.next) {
                p = p.next;
                ++pSteps;

                //  p q        
                if (p == q) {
                    //         ，      
                    if (pSteps != qSteps) {
                        return pSteps - 1;
                    } else {
                        //       ，    
                        break;
                    }
                }
            }

            p = head; //      
            pSteps = 0;
        }

        //            ，     
        return -1;
    }