연결된 목록에 루프가 있는지 여부를 확인하는 알고리즘

Question

그래서 최근에 사이클이 연결된 목록에 있는지 여부를 확인하는 알고리즘을 발견했습니다.

public boolean hasCycle(ListNode head) { 
    if (head == null) { 
     return false; 
    } 
    ListNode fast = head; 
    ListNode slow = head; 
    while (fast != null) { 
     if (fast.next == null) { 
      return false; 
     } 
     if (fast.next == slow) { 
      return true; 
     } 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    return false; 
} 

이 알고리즘의 정확성을 증명하려고, 나는 아이디어를 제공 :주기의 경계 "가"입니다 가정 , 만나는 두 개의 포인터까지의 시간을 다음과 같이 코드는 "티". 은 "빠른"노드의 속도가 "느린"노드로 두 배 빠른 속도로 이동하기 때문에, 우리는 수학적 관계를 얻을 수 있습니다 :

2t 모드 A는 = t A가

는 상수가 나타내는 자 "는"있는 MOD 둘레와 "t"는 1,2,3 ... 일 수 있습니다. 그런 다음, "a"값이 무엇이든 위의 방정식을 풀 수있는 "t"를 항상 찾을 수 있다는 것을 어떻게 증명할 수 있습니까?

Answer 1

당신은 올바른 길을 걷고 있습니다! 힌트 : 반복 후 수식은 어떻게됩니까? 두 포인터 가정

는

Answer 2

주기 내에 동일한 지점에서 시작한다 (이것은 회의의 계산에 포함되지 않는다)

2t = t (a)

=>2t - t = 0 (a)

=> t에서 의미 t = 0 (a)

= a * k, 경과 시간이 사이클 길이의 배수가되면 양쪽 포인터가 시작 지점에서 만나게됩니다.

시간이 모든 k>1에 대한 k*a에 같을 때, 빠른 포인터가 두 배 빠르게 실행되는 동안 느린 포인터가 정확하게 K주기가 긴 실행, 그래서 긴 2K 사이클을 실행하기 때문에 그것은 모든 a >= 2 마찬가지입니다, 여전히 그들은에서 만나 출발점 인 같은 지점.