Floyd의주기 감지 알고리즘 구현이 올바르지 않습니까?

Question

나는 연결리스트의주기를 검출하기위한 다음과 같은 코드가 있습니다 :

public Class Node { 
    Object data; 
    Node next = null; 
} 

boolean containCycle() { 
    boolean retVal = true; 
    Node head = this; 
    Node slower = head; 
    Node faster = head; 

    if(faster != null && faster.next != null) { 
     faster = faster.next; 
    } else { // there is only one element or zero element 
     retVal = false; 
    } 

    if (faster.next != null) { 
     faster = faster.next; 
    } else { // there are only 2 elements 
     retVal = false; 
    } 

    while (slower != faster && slower != null && faster != null) { 
     faster = (faster.next != null && faster.next.next != null) ? faster.next.next : null; 
     slower = (slower.next != null) ? slower.next : null; 
    } 

    if (slower == faster) { 
     retVal = true; 
     System.out.printf("The two pointers meet at: %d\n", faster.data); 
    } else { 
     retVal = false; 
    } 

    if (retVal) { // this is the part for detecting where the loop begins 
     slower = head; 
     while(slower.next != faster.next) { 
      slower = slower.next; 
      faster = faster.next; 
     } 
     System.out.println("The cycle starts at: " + slower.data); 
    } 

    return retVal; 
} 

이 코드는 실제로 루프가 나는 코드에 주석하는, 시작되는 위치를 감지 시작 부분까지 잘 실행됩니다. 여하튼, 이것은 무한 루프로 진행됩니다.

이것이 Java에서 참조로 전달되는 것으로 여겨집니다. 루프를 감지하는 동안 head이 참조하는 값을 업데이트합니까? 나는 아이디어가 없다. 도와주세요!

Answer 1

정확한 알고리즘을 모르지만 다음과 같은 방법으로 회의 지점을 찾을 수 있습니다.

더 빠르고 더 빠르게 만나는 노드를 회의 지점이라고합시다.

두 개의 포인터가 머리에서 시작하고 다른 포인터가 회의 지점에서 시작됩니다. 그리고 헤드에서 미팅 포인트 (이 카운트를 a이라고 부름)와 미팅 포인트의 다음 노드를 미팅 포인트로 통과해야하는 노드 수를 유지하십시오. (이 수를 b이라고 부르 자)

이제이 두 수의 차이 |a-b|은 공통 부분을 나타냅니다. (즉, 루프의 시작과 느리고 빠른 회의 지점 사이의 부분). 다른

이제 다시 afresh.Reset에게 두 개의 포인터, 머리에 하나 미팅 포인트 + 1

예를 들어 a>b 경우 다른 시작 머리에서 포인터를 이동 |a-b| 시간 + 1 |a-b| 회의 piont에서 포인터를 이동 타임스.

두 개의 포인터가 만나기 전까지 두 포인터를 함께 움직입니다. 두 개의 연결리스트를 가지고 그들이 어떤 노드에서 병합하고 해당 노드를 식별하기 위해 필요로하는 곳에

당신이 찾고있는 무엇 때문에이

을 설명하는 또 다른 방법은 경우와 유사하다. 두 개의 링크 된 목록의 시작점 만 있으면됩니다.

그래서 head1부터 시작하여 목록 끝까지 계산합니다. 다음으로 head2에서 시작하여 목록 끝까지 계산합니다.

길이의 차이를 계산하십시오. 더 긴 경로 diff 시간을 늘리십시오. 그리고 두 포인터가 만날 때까지 더 짧은 경로 헤드와 diff에서 시작하여 포인터를 이동하십시오.

이것은 본질적으로 다른 경우에 수행하는 것과 같습니다.