사이클 링크리스트에서 사이클 시작 노드를 찾는 방법이 어떻게 설명되어 있습니까?

사이클 링크리스트에서 사이클 시작 노드를 찾는 방법이 어떻게 설명되어 있습니까?

---

Tortoise와 Hare의 회의는 루프가 존재한다는 것을 이해하지만 토끼를 회의장에 유지하면서 거북이를 연결 목록의 시작 부분으로 이동 한 다음 한 번에 한 단계 씩 이동하면 사이클의 시작점에서 만나게됩니까?

---

이것은 사이클 감지를위한 Floyd의 알고리즘입니다 . 알고리즘의 두 번째 단계에 대해 묻습니다. 사이클의 일부인 노드를 찾으면 사이클의 시작 을 어떻게 찾 습니까?

Floyd 알고리즘의 첫 번째 부분에서, 토끼는 거북이의 모든 단계마다 두 단계 씩 움직입니다. 거북이와 토끼가 만나면주기가 있고 만나는 지점이주기의 일부이지만 반드시주기의 첫 번째 노드는 아닙니다.

거북이와 토끼가 만나면 X _i = X _2i가 되도록 가장 작은 i (거북이 걸음 수)를 찾았습니다 . mu가 X ₀ 에서 사이클 시작 까지의 단계 수를 나타내고 람다는 사이클 길이를 나타냅니다. 그런 다음 i = mu + a lambda 및 2i = mu + b lambda입니다. 여기서 a 및 b는 거북이와 토끼의주기 횟수를 나타내는 정수입니다. 두 번째 방정식에서 첫 번째 방정식을 빼면 i = (ba) * lambda가되므로 i는 람다의 정수배입니다. 따라서 X _{i + mu} = X _mu 입니다. X _i 는 거북이와 토끼의 만나는 지점을 나타냅니다. 거북이를 시작 노드 X로 다시 옮기면₀ , 거북이와 토끼가 같은 속도로 계속되도록합니다. mu 추가 단계 후에 거북이가 X _mu에 도달 하고 토끼가 X _{i + mu} = X _mu에 도달 하므로 두 번째 미팅 포인트는 시작의 시작을 나타냅니다. 주기.

---

http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare 에서 제공되는 사이클 감지 알고리즘을 명확하게 설명하겠습니다 .

작동 원리

위의 다이어그램 에서처럼 주기로 목록의 시작을 가리키는 거북이와 토끼 (포인터 이름)를 보자.

한 번에 거북이를 한 단계 씩 움직이고 한 번에 두 단계 씩 토끼를 타면 결국에는 만나게 될 것이라는 가설을 세우십시오. 먼저이 가설이 사실임을 보여 드리겠습니다.

그림은주기가있는 목록을 보여줍니다. 주기는 길이이며 n처음에는 m주기에서 멀어집니다. 또한 미팅 포인트가 k사이클 시작과 거북이에서 멀어지고 거북이가 i총 걸음을 내딛을 때 토끼가 만나는 것으로 가정 해 봅시다 . 2i그때 까지는 총 걸음을 내딛었을 것 입니다.

다음 두 가지 조건이 충족되어야합니다.

1) i = m + p * n + k

2) 2i = m + q * n + k

첫 번째는 거북이가 i단계 를 움직이고이 단계에서 i먼저주기에 도달 한다고 말합니다 . 그런 다음 p양수에 대한 사이클 시간을 거 칩니다 p. 마지막으로 k토끼를 만날 때까지 더 많은 노드를 통과 합니다.

토끼도 마찬가지입니다. 2i단계를 이동 하고이 2i단계 에서 먼저주기에 도달합니다. 그런 다음 q양수에 대한 사이클 시간을 거 칩니다 q. 마지막으로 k거북이를 만날 때까지 더 많은 노드 로 넘어갑니다 .

토끼가 거북이 속도의 두 배로 이동함에 따라 회의 지점에 도달했을 때 시간이 일정합니다.

따라서 간단한 속도, 시간 및 거리 관계를 사용하면

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

m, n, k, p, q 중에서 처음 두 가지는 주어진 목록의 속성입니다. 이 방정식을 참으로 만드는 k, q, p에 대해 적어도 하나의 값 집합이 있음을 나타낼 수 있다면 가설이 올바른 것입니다.

이러한 솔루션 세트 중 하나는 다음과 같습니다.

p = 0

q = m

k = m n - m

이러한 값이 다음과 같이 작동하는지 확인할 수 있습니다.

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

이 세트 들어 i있다

i = m + p n + k

=> m + 0 * n + mn - m = mn.

물론, 이것이 반드시 가장 작은 것은 아니라는 것을 알아야합니다. 다시 말해, 거북이와 토끼는 이미 여러 번 전에 만났을 수도 있습니다. 그러나 우리는 그들이 적어도 어느 시점에서 한 번 만나는 것을 보여주기 때문에 가설이 정확하다고 말할 수 있습니다. 따라서 한 단계 씩 한 단계 씩 이동하고 다른 하나는 한 번에 두 단계 씩 이동하면 만나야합니다.

이제 우리는 사이클의 시작 부분을 찾는 방법 인 알고리즘의 두 번째 부분으로 이동할 수 있습니다.

사이클 시작

거북이와 토끼가 만나면 거북이를 목록의 시작 부분으로 되돌리고 토끼가 만나는 곳 (주기 시작에서 k 단계)을 유지하십시오.

가설은 우리가 그것들을 같은 속도 (둘 다 1 단계)로 움직이게하면, 그들이 다시 처음 만날 때 사이클이 시작된다는 것입니다.

이 가설을 증명해 봅시다.

먼저 오라클이 m이 무엇인지 알려줍니다.

그런 다음 m + k 단계를 이동 시키면 거북이가 원래 만나는 지점에 도착해야합니다 (주기에서 시작하여 k 단계-그림 참조).

이전에 우리는 그것을 보여 주었다 m + k = (q - 2p) n.

m + k 스텝은 사이클 길이 n의 배수이므로, 평균적으로, 토끼는 사이클 (q-2p) 시간을 거쳐 다시 같은 지점으로 돌아갑니다 (k 사이클이 사이클 시작에서 멀어짐).

이제 m + k 단계를 움직이게하는 대신 m 단계 만 움직이게하면 거북이가주기 시작에 도달하게됩니다. 토끼는 (q-2p) 회전을 완료하는 데 k 스텝이 부족합니다. 사이클 시작 앞에서 k 단계를 시작했기 때문에, 토끼는 사이클 시작에 도달해야합니다.

결과적으로, 그들은 처음 몇 번의 단계 후에 시작하는 사이클에서 만날 필요가 있다고 설명합니다 (거북이 m 단계 후에 사이클에 도착했을 때 이미 처음부터 거북이를 볼 수 없었기 때문에 처음으로 사이클).

이제 우리는 그것들이 만나기 전까지 이동해야하는 단계의 수가 목록의 시작에서 사이클 시작까지의 거리 인 것으로 판명되었습니다. 물론, 알고리즘은 m이 무엇인지 알 필요가 없습니다. 그것은 그들이 만나기 전까지 한 번에 한 걸음 씩 거북이와 토끼를 움직일 것입니다. 미팅 포인트는 사이클 시작이어야하고 단계 수는 사이클 시작까지의 거리 (m) 여야합니다. 리스트의 길이를 알고 있다고 가정하면,리스트 길이에서 m을 빼는주기의 길이를 계산할 수도 있습니다.

---

이 이미지를 참조하십시오 :

회의 전에 slowPointer로 이동 한 거리 = x + y

회의 전에 fastPointer로 이동 한 거리 = (x + y + z) + y = x + 2y + z

fastPointer는 slowPointer 속도의 두 배로 이동하므로 미팅 포인트에 도달 할 때 시간이 일정 합니다.

따라서 간단한 속도, 시간 및 거리 관계를 사용하여 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

따라서 slowPointer 를 링크 된 목록의 시작 으로 이동 하고 slowPointer와 fastPointer가 한 번에 하나의 노드를 이동 하게하여 둘 다 같은 거리 를가집니다 .

링크 된 목록에서 루프가 시작되는 지점에 도달합니다.

---

_{올드 스님의 간단하고 과소 평가 된 답변 은 빠른 러너가 단일 전체 사이클 만 완료했을 때 사이클을 찾는 방법을 설명합니다. 이 답변에서는 느린 러너가 루프에 들어가기 전에 빠른 러너가 루프를 여러 번 실행 한 경우를 설명합니다.}

---

동일한 이미지 사용하기 :

빠른 러너가 느리고 빠른 만남 전에 루프 m 을 실행했다고 가정 해 봅시다 . 이것은 다음을 의미합니다.

• 느린 거리 : x + y
• 빠른 거리 : x + m (y + z) + y 즉 그들이 만나는 여분의 y

빠른 속도는 두 배의 느린 속도로 달리고 같은 시간 동안 달리고 있기 때문에 느린 거리를 두 배로 늘리면 거리가 빠르게 움직입니다. 그러므로,

• 2 (x + y) = x + m (y + z) + y

x를 구하면

x = (m-1) (y + z) + z

실제 시나리오에서는 x = (m-1) 전체 루프 실행 + 추가 거리 z를 의미 합니다.

따라서 하나의 포인터를 목록의 시작 부분에 놓고 다른 하나를 회의 지점에두면 동일한 속도로 이동하면 루프 포인터가 루프의 m-1 런을 완료 한 다음 다른 포인트 를 만나게됩니다 루프 시작에서 바로 포인터.

---

첫 번째 충돌시 거북이 는 위 그림과 같이 m + k 단계만큼 이동했습니다 . 토끼는 거북이보다 두 배 빠르게 움직입니다. 즉, 토끼는 2 (m + k) 걸음을 이동했습니다. 이러한 간단한 사실을 통해 다음 그래프를 도출 할 수 있습니다.

이 시점에서 우리는 거북이를 처음으로 다시 이동시키고 토끼와 거북이가 한 번에 한 단계 씩 움직여야한다고 선언합니다. 정의에 따르면, m 단계 후에 거북이가 사이클 시작에있게됩니다. 헤어는 어디입니까?

토끼는 또한 사이클의 시작에있을 것입니다. 이것은 두 번째 그래프에서 분명합니다. 거북이가 처음으로 돌아 왔을 때, 토끼는 마지막주기 에서 k 단계 였습니다 . m 단계 후 , 토끼는 다른주기를 완료하고 거북이와 충돌했습니다.

---

매우 간단합니다. 상대 속도로 생각할 수 있습니다. 토끼가 두 개의 노드를 움직이고 거북이가 한 노드를 움직이면 거북이 토끼가 한 노드를 움직이고 있습니다 (거북이 있다고 가정). 따라서 순환 연결 목록에서 하나의 노드를 이동하면 해당 지점에서 다시 만나게됩니다.

원형 연결리스트 내에서 연결된 점을 찾은 후, 이제 두 연결리스트 문제의 교점을 찾는 문제가 줄어 듭니다.

---

접근하다:

두 가지 포인터가 있습니다.

• 한 번에 한 노드 씩 이동하는 느린 포인터.
• 한 번에 두 노드를 이동하는 빠른 포인터.

두 포인터가 만나면 루프가 있음을 증명합니다. 일단 충족되면 노드 중 하나가 헤드를 가리킨 다음 두 노드가 한 번에 하나씩 진행됩니다. 그들은 루프의 시작에서 만날 것입니다.

이론적 근거 : 두 사람이 원형 트랙을 걸을 때 한 사람이 다른 사람보다 두 배나 빠른 속도로 어디에서 만날까요? 그들이 정확히 어디서 시작했는지.

이제 빠른 러너가 스텝 랩 k에서 헤드 스타트 단계를 가지고 있다고 가정 하십시오 n. 그들은 어디서 만날 것인가? n-k단계적으로 정확 합니다. 느린 주자가 (n-k)단계 를 다룰 때 빠른 주자가 k+2(n-k)단계를 다룰 것 입니다. ( 즉, k+2n-2k단계 즉 2n-k단계 ). 즉 (n-k)단계 (경로는 원형이며 우리는 그들이 만나는 라운드 수에 대해 걱정하지 않습니다; 우리는 그들이 만나는 위치에 관심이 있습니다).

이제 빠른 러너는 어떻게 맨 k먼저 단계를 시작 했습니까? 루프 시작에 도달하는 데 많은 단계가 느린 러너가 필요했기 때문입니다. 따라서 루프의 시작은 헤드 노드에서 k 단계입니다.

참고 : 두 포인터가 만나는 노드 k는 루프 시작 (루프 내부) k에서 멀어지고 헤드 노드는 루프 시작에서 멀어집니다. 따라서 봇에서 1 단계 속도로 같은 속도로 포인터를 진행하면 루프가 시작될 때 만나게됩니다.

나는 그것이 간단하다고 생각합니다. 모호한 부분이 있으면 알려주십시오.

---

자, 토끼와 거북이가 사이클 시작에서 k 단계 떨어진 지점에서 만나고, 사이클 시작 전의 단계 수는 mu이고 사이클 길이는 L이라고 가정합니다.

이제 미팅 장에서->

거북이로 덮인 거리 = mu + a * L + k-방정식 1

(사이클의 시작에 도달하기위한 단계 + 사이클의 'a'반복 + 사이클의 시작부터 k 단계를 포함하기 위해 수행 된 단계) (a는 양의 상수)

토끼로 덮힌 거리 = mu + b * L + k-식 2

(사이클의 시작에 도달하기 위해 취한 단계 + 사이클의 'b'반복을 덮기 위해 취한 단계 + 사이클의 시작부터 k 단계) (여기서 b는 양의 상수이고 b> = a)

따라서 토끼가 덮는 여분의 거리는 = 식 2-식 1 = (ba) * L입니다.

이 거리는 토끼가 거북이보다 2 배 빠르게 이동하기 때문에 출발점에서 거북이의 거리와 동일합니다. 사이클의 다중 순회를 포함하지 않는 경우 처음부터 미팅 포인트의 거리 인 'mu + k'와 같습니다.

따라서 mu + k = (ba) * L

따라서이 시점부터 mu 단계는주기 시작으로 돌아갑니다 (주기 시작부터 k 단계가 이미 미팅 포인트에 도달 했으므로). 이는 동일한주기 또는 후속주기에서 발생할 수 있습니다. 따라서 거북이를 연결된 목록의 시작 부분으로 옮기면 사이클의 시작점에 도달하기 위해 뮤 단계가 필요하고 토끼는 사이클의 시작 부분에 도달하기 위해 뮤 단계를 수행하므로 둘 다에서 만나게됩니다. 사이클의 시작점.

추신 : 솔직히, 나는 내 생각에 원래의 포스터와 같은 질문을했고 첫 번째 대답을 읽었습니다. 몇 가지 사항을 분명히했지만 최종 결과를 명확하게 얻을 수 없었기 때문에 내 방식대로 노력했습니다. 이해하기 쉽다는 것을 알았습니다.

---

이미지 크레디트

호출 포인터가 따르는 링크의 수와 느린 포인터를 한 링크로, 빠른 포인터를 두 링크로 이동하는 데 걸리는 반복 횟수입니다. 길이 C의주기 전에 사이클 오프셋 k = 0에서 C-1로 레이블이 지정된 N 개의 노드가 있습니다.

사이클 시작에 도달하려면 N 시간과 거리가 느려집니다. 이는 사이클에서 N 거리를 빠르게 가져옵니다 (N은 회전, N은 회전). 따라서 시간 N에서 저속은 사이클 오프셋 k = 0에, 고속은 사이클 오프셋 k = N mod C에 있습니다.

N mod C가 0이면, 느리고 빠름이 일치하고 사이클은 시간 N과 사이클 위치 k = 0에서 발견됩니다.

N mod C가 0이 아닌 경우, 빠른 속도는 이제 느리게 따라 잡아야합니다. N은 사이클에서 C- (N mod C) 거리입니다.

1의 느린 속도마다 2 씩 빠르게 이동하므로 반복 할 때마다 거리가 1 씩 줄어들 기 때문에 시간 N에서 빠른 속도와 느린 속도 사이의 거리 (C- (N mod C))만큼 추가 시간이 걸립니다. 슬로우는 오프셋 0에서 움직이기 때문에 이것이 만나는 오프셋이기도합니다.

따라서 N mod C가 0이면 사이클 시작시 N 반복 후에 위상 1이 정지합니다. 그렇지 않으면,주기 C로 오프셋 C- (N mod C)에서 N + C- (N mod C) 반복 후에 위상 1이 멈 춥니 다.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

2 단계 : 느리게 순환하려면 N 단계를 더 걸립니다.이 시점에서 (현재 단계 당 1 개씩 이동) (C- (N mod C) + N) mod C = 0입니다. 2 단계 후 사이클 시작시

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

완전성을 위해 3 단계는 사이클을 통해 한 번 더 이동하여 사이클 길이를 계산합니다.

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

---

루프 문제로 문제를 줄인 다음 초기 문제로 돌아갑니다.

다음 설명이 더 직관적이라는 것을 알았습니다.

1. 머리 ( O ) 에서 시작하는 2 개의 포인터 ( 1 = 거북이와 2 = 토끼)를 취하십시오 .1 은 스텝 길이가 1 이고 2 는 스텝 길이가 2 입니다. 1 이 해당 사이클의 시작 노드 ( A )에 도달 하는 순간을 생각하십시오 .

   우리는 다음 질문에 대답하고 싶습니다. "1이 A에있을 때 2는 어디에 있습니까?" .

   따라서 OA = a자연수 ( a >= 0)입니다. 그러나 다음과 같은 방법으로 쓸 수있다 : a = k*n + b여기서 a, k, n, b are natural numbers:

   • n = 사이클 길이
   • k >= 0 = 상수
   • 0 <= b <= n-1

   그것은 의미합니다 b = a % n.

   예 : if a = 20and n = 8=> k = 2and b = 4because 20 = 2*8 + 4.

   1 이 적용되는 거리는 입니다 d = OA = a = k*n + b. 그러나 동시에 2 개가 포함 D = 2*d = d + d = OA + d = OA + k*n + b됩니다. 이것은 2 가 A에 있을 때 가려야 함을 의미합니다 k*n + b. 당신이 볼 수 있듯이, k바퀴의 수는 있지만, 그 랩을 한 후, 2 될 것 b를 어디까지 A. 그래서에서 우리가 발견 한 2 때입니다 1 A.하자 호출 그 시점에 B, AB = b.

   

2. 이제 문제를 원으로 줄입니다. 문제는 "만남의 장소는 어디입니까?"입니다. . 그 C 는 어디에 있습니까 ?

   

   모든 단계에서, 2 에서의 거리 감소 (1) 과 함께 1있기 때문에 (하자의 말 미터) 1 에서 더 받고 2 과를 1, 그러나 동시에 2 가까이로 이동 1 가 2.

   따라서 교차점은 1 과 2 사이의 거리 가 0 이 될 때 입니다. 이것은 2 가 n - b거리를 줄인다는 것을 의미합니다 . 이를 달성하기 위해 1 은 n - b단계를 수행하고 2 는 2*(n - b)단계를 수행합니다.

   따라서 교차점 n - b은 A (시계 방향)에서 멀어 집니다. 이는 2를 만나기 전까지 1 의 거리이기 때문 입니다. => 사이의 간격 C 와 A는 이고 때문에 하고 . 그렇게 생각하지 마십시오 때문에, 거리가 사소한 수학적 거리 아니라, 사이 단계의 수를 와 C ( A는 시작 지점이고, C는 엔드 포인트입니다).CA = bAC = AB + BC = n - bCA = n - ACAC = CAAC

3. 이제 초기 스키마로 돌아 갑시다.

   우리는 알고 a = k*n + b및 CA = b.

   2 개의 새로운 포인터 1 ' 과 1' '을 취할 수 있는데, 여기서 1' 은 헤드 ( O ) 에서 시작 하고 1 '' 은 교차점 ( C ) 에서 시작합니다 .

   반면 1 ' 부터 진행 O 에 , '1 ' 부터 진행 C 에 및 마무리 계속 랩. 따라서 교점은 A 입니다.k

   

   

---

포인터가 그림과 같이 점 P에서 만나면 거리 Z + Y는 점 P이고 X + Y는 점 P이기도합니다. 이는 Z = X를 의미합니다. 그렇기 때문에 한 포인터를 P에서 계속 움직이고 시작점 (S)에서 만나기 전까지 다른 포인터를 움직입니다. 즉 같은 거리 (Z 또는 X)를 같은 점 M (P에서 거리 Z, S에서 거리 X)으로 이동하는 것이 루프 시작. 단순한!

---

위의 모든 분석을 통해, 당신이 예제별로 배우는 사람이라면, 나는 다른 사람들이 설명하려고 시도한 수학을 설명하는 간단한 분석과 예제를 작성하려고했습니다. 간다!

분석:

우리가 두 개의 포인터를 가지고 있다면, 하나는 다른 것보다 더 빠르며 함께 움직이면, 결국주기를 나타 내기 위해 다시 만나거나,주기가 없음을 나타 내기 위해 null이됩니다.

사이클의 시작점을 찾으려면 ...

1. m 머리에서주기의 시작까지의 거리;
2. d 주기의 노드 수;
3. p1 느린 포인터의 속도;

4. p2더 빠른 포인터의 속도, 예. 2는 한 번에 두 개의 노드를 통과하는 것을 의미합니다.

   다음 반복을 관찰하십시오.

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

위의 샘플 데이터에서 더 빠르고 느린 포인터가 만날 때마다 m사이클 시작에서 조금 떨어져 있음을 쉽게 알 수 있습니다 . 이 문제를 해결하려면 빠른 포인터를 다시 헤드에 놓고 속도를 느린 포인터의 속도로 설정하십시오. 다시 만나면 노드가주기의 시작입니다.

---

의 말을하자,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

우리는 2 개의 포인터 A와 B를 가지고 있습니다. A는 1x 속도로, B는 2x 속도로 작동하며, 둘 다 처음부터 시작합니다.

A가 N [0]에 도달하면 B는 이미 N [m]에 있어야합니다. (참고 : A는 m 단계를 사용하여 N [0]에 도달하고 B는 m 단계 더 나아가 야합니다)

그런 다음 A는 k에 더 많은 단계를 실행하여 B와 충돌합니다. 즉 A는 N [k]에 있고 B는 N [m + 2k]에 있습니다 (참고 : B는 N [m]부터 시작하여 2k 단계 동안 실행해야 함)

N [k] 및 N [m + 2k]에서 충돌 B는 각각 k = m + 2k를 의미하므로 k = -m

따라서 N [k]에서 N [0]으로 되돌아 가려면 m 개의 단계가 더 필요합니다.

간단히 말해서 충돌 노드를 찾은 후 m 단계를 더 실행하면됩니다. 처음부터 실행할 포인터와 충돌 노드에서 실행되는 포인터를 가질 수 있습니다. m 단계 후에 N [0]에서 만나게됩니다.

따라서 의사 코드는 다음과 같습니다.

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

---

나는 그들이 만나면 그것이 출발점이되는 것이 사실이라고 생각하지 않습니다. 그러나 그렇습니다. 다른 포인터 (F)가 이전의 미팅 포인트에 있었다면, 그 포인터보다 루프의 시작과 목록의 시작에서 시작한 포인터 대신 루프의 끝에있을 것입니다. 루프가 시작되면 끝납니다. 예를 들어 :

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}

---

고등학교에서 가르치는 상대 속도에 대한 간단한 설명 -물리학 101 / 운동학 강의.

1. 연결된 목록의 시작에서 원의 시작까지의 거리가 x홉 이라고 가정합시다 . 원의 시작점을 점이라고합니다 X(모두-위 그림 참조). 또한 원의 총 크기가 N 홉이라고 가정합니다.

2. 토끼의 속도 = 2 * 거북이의 속도. 그래서 1 hops/sec그리고 2 hops/sec각각

3. 거북이가 원의 시작점에 도달 할 때 X, 토끼는 그림의 한 x지점 Y에서 더 멀리 홉핑 해야합니다 . (토끼가 거북이의 두 배 거리를 여행했기 때문에).

4. 따라서 X에서 Y까지 시계 방향으로 남은 호의 길이는 N-x입니다. T는 자신도 그들을 만날 수있을하는 토끼와 거북이 사이에 적용되는 상대적인 거리 될 일이 . 이 상대 거리는 시간, t_m즉 만날 시간으로 커버 될 것이라고 가정하자 . 상대 속도는 (2 hops/sec - 1 hops/sec)즉 1 hops/sec. 따라서 상대 거리 = 상대 속도 X 시간을 사용하면 t= N-x초입니다. N-x거북이와 토끼의 만남에 도달하려면 시간 이 걸립니다 .

5. 이제 N-x시간과 1 hops/sec속도로 초창기의 거북이가 XNx 홉을 가리켜 회의 지점에 도달합니다 M. 그래서, 합류점 그 수단 M에있다 N-x홉은 시계 반대 X가 있음 => (상기 의미 함) = x시점에서 남은 거리 M를 X시계 방향.

6. 그러나 x또한 X연결리스트의 시작부터 도달 할 거리 입니다.

7. 이제 우리는 어떤 홉 수에 x해당 하는지 상관하지 않습니다 . LinkedList의 시작 부분에 거북이 하나를 넣고 미팅 포인트에 거북이 하나를 꽂아 M홉 / 걸리면 X우리가 필요한 포인트 (또는 노드) 인 point 에서 만날 것 입니다.

---

이것을 다이어그램으로 작업하면 도움이 될 것입니다. 방정식없이 문제를 설명하려고합니다.

1. 우리가 토끼와 거북이를 둥글게 돌리고 토끼가 두 번 거북이를 뛰면 토끼의 끝이 한 바퀴 끝날 때 절반이됩니다. 토끼 거북이에서 2 바퀴가 끝날 때 1 바퀴가 걸렸을 것입니다. 이것은 토끼가 세 번 달리는 것처럼, 토끼 1 랩이 거북이의 1/3과 동일하므로 토끼 3 바퀴가 끝날 때 3 바퀴가 끝났을 때 만나는 것처럼 모든 속도에 적용됩니다.
2. 이제 루프 전에 m 단계를 시작하면 더 빠른 토끼가 루프에서 앞서 시작한다는 것을 의미합니다. 따라서 거북이가 루프의 시작점에 도달하면 토끼는 m 스텝 전방 루프이며 만나면 루프가 시작되기 전에 m 스텝이됩니다.

---

루프 전에 k 단계가 있습니다. 우리는 k가 무엇인지 알지 못하고 알 필요가 없습니다. k만으로도 추상적으로 작업 할 수 있습니다.

--k 단계 후

----- T는 사이클 시작입니다

----- H는 k 단계로 사이클입니다 (그는 총 2k가되었으므로 k를 루프에 넣었습니다)

** 그들은 이제 루프 크기입니다-k 떨어져

(k == K == mod (loopsize, k)-예를 들어, 노드가 5 노드 주기로 2 단계 인 경우 7, ​​12 또는 392 단계로 진행되므로주기가 얼마나 큰지 krt가 아닙니다. 인수 분해

하나는 다른 것보다 두 배 빠르게 이동하기 때문에 단위 시간당 1 단계의 속도로 서로를 따라 잡기 때문에 루프 크기-k에서 만날 것입니다.

이것은 k 개의 노드가 사이클의 시작점에 도달하는 것을 의미하므로 헤드에서 사이클 스타트까지의 거리와 충돌에서 사이클 스타트까지의 거리는 동일합니다.

이제 첫 번째 충돌 후 T를 머리로 다시 움직입니다. T와 H는 각각 1의 속도로 이동하면 사이클 시작시 만나게됩니다. (둘 다 k 단계)

이는 알고리즘이 다음을 의미합니다.

• 헤드에서 T = t.next 및 H.next.next가 충돌 할 때까지 이동합니다 (T == H) (사이클이 있음)

// 루프의 길이를 계산하여 루프 헤드에서 k = 0 또는 T와 H가 만나는 경우를 처리합니다.

-카운터로 T 또는 H를 움직여 사이클의 길이를 센다

-포인터 T2를리스트의 헤드로 이동

사이클 단계의 포인터 길이 이동

다른 포인터 H2를 머리로 이동

-사이클 시작시 T2와 H2가 나란히 움직일 때까지 움직입니다.

그게 다야!

---

이미 이것에 대한 많은 답변이 있지만 한 번 더 시각적으로 직관적 인 다이어그램을 생각해 냈습니다. 아마도 그것은 다른 사람들을 도울 수 있습니다.

나를위한 주요한 순간은 :

• T (거북)을 T1 (사전 루프) 및 T2 ( 루프 내 )로 분할 합니다.

• H 에서 T 를 빼면 시각적으로 겹칩니다. 남아있는 것 ( H-T = H ' )은 T와 같습니다 .

• 나머지 수학은 매우 간단합니다.

---

이 문제에 대해 이미 받아 들여진 답변이 있지만 여전히 유동적 인 방식으로 답변하려고 노력할 것입니다. 가정 :

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

이제 처음부터 't'후에 토끼와 거북이가 만나도록하십시오.

관찰 :

만약, 거북이에 의해 이동 한 거리 = v * t = x + (bk) (즉)

그런 다음, 토끼가 이동 한 거리 = 2 * v * t = x + (b-k) + b (토끼가 이미 루프 된 부분을 통과 했으므로)

이제 모임 시간이 동일합니다.

=> x + 2 * b-k = 2 * (x + b-k)

=> x = k

이것은 루프되지 않은 경로의 길이가 루프의 시작점과 두 지점이 만나는 지점의 거리와 동일하다는 것을 의미합니다.

---

만남의 배후에있는 수학을 고려한다면, 둘 다 출발점에서 만날 것임을 실제로 증명하는 것은 쉽습니다.
먼저 m 은 링크 된 목록에서 사이클의 시작점을 나타내고, n 은 사이클의 길이를 나타냅니다. 토끼와 거북이가 만나기 위해

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

이것을 더 수학적으로 진술 :

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

그래서 그들은 t의 시간에서 만나고 이것은 사이클 길이의 배수이어야한다. 이것은 그들이 어떤 위치에서 만난다는 것을 의미합니다 (t-m) modulo n = (0-m) modulo n = (-m) modulo n.

따라서 이제 질문으로 돌아갑니다. 링크 된 목록의 시작 부분에서 하나의 포인터를 이동하고 교차점에서 다른 포인터를 이동하면 m 단계 후에 우리는 토끼 (주기 내에서 이동)가 다음과 같은 지점에 도달하게됩니다 ((-m) + m) modulo n = 0 modulo nm 단계 후에는 사이클의 시작 부분에 도달하고 거북이가 링크 된 목록의 시작 부분에서 m 단계를 가로 지르므로 거기에서 거북이가 만나는 것을 볼 수 있습니다 .

참고로, 우리는 또한 이러한 방식으로 교차 시간을 계산할 수 있습니다. 조건 t = 0 modulo n은 사이클 길이의 배수 인 시간에 만나고 또한 t 가 m 보다 커야 함 을 알려줍니다. 사이클. 따라서 걸리는 시간 은 m 보다 큰 n 의 첫 번째 배수와 같습니다 .

---

포인터가 점 y와 z의 교차점에서 만나고 있다고 가정하십시오.

n과 m은 만나기 전에 각각 더 빠르고 느린 포인터의 루프 수입니다.

나머지 증거는 이미지를 참조하십시오. 링크 된 목록에서 루프의 시작점 찾기

참고 URL : https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work