#LeetCode 142 Linked List Cycle II

まず第141題を参考にして,チェーンテーブルにループがあるか否かを判断する.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode walk = head;
        ListNode run = head;
        while(run.next!=null && run.next.next!=null){
            walk = walk.next;
            run = run.next.next;
            if(walk==run) return true;
        }
        return false;
    }
}

全体的な考え方は、2つのポインタがあり、1つは1歩歩くたびに、1つは2歩歩くたびに、最後の2つのポインタが出会うことができれば、チェーンテーブルにリングが存在するに違いない.142題を見て、ループがあるかどうかを判断するだけでなく、ループの開始ノードに戻ります.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode walk = head;
        ListNode run = head;
        while(run.next!=null && run.next.next!=null){
            walk = walk.next;
            run = run.next.next;
            if(walk==run){
                ListNode slow = head;
                while(slow!=walk){
                    slow = slow.next;
                    walk = walk.next;
                }
                return slow;
            }
        }
        return null;
    }
}

まずコードを見て、全体の構想は141題とあまり違わないが、ただループがあると判断した後、さらに一歩操作しなければならない.この操作の意味は以下の通りである.2つのポインタrunとwalkを仮定すると

  walk  
A+B （A             ，B        ）

  run  2(A+B) ,  run     

リング長をNとすると

A+B+N=2A+2B
N=A+B

このとき、最初から歩くポインタをもう一つ追加します.slow、彼がリングまで歩いた距離はAです.では、slowはA歩を歩いて、walkはA+B+A歩を歩いて、N=A+Bを引いて、slowとwalkは必ずAのところに合流します.つまり、彼らが出会った場所はリングの始まりです.