검출하기 시작하의 루프가 단독으로 연결되는 링크 목록?

Question

어떤 방법을 찾기 시작하의 루프에서 링크를 사용하여 목록 지 않을 두 개 이상의 포인터? 내가 원하지 않는 방문하는 모든 노드 표시 본 보고 처음 노드 이미 볼 수 있습니다.할 수 있는 다른 방법이 있습니까?

Answer 1

이 정확한 질문을 인터뷰 퀴즈 질문으로 들었습니다.

가장 우아한 해결책은 다음과 같습니다.

첫 번째 요소에 두 포인터를 넣으십시오 (A와 B라고 부릅니다)

그런 다음 계속 반복 ::

• 다음 요소로 A를 전진 시키십시오
• 다음 요소로 다시 전진하십시오
• 다음 요소로 B를 전달하십시오

포인터를 업데이트 할 때마다 A와 B가 동일한지 확인하십시오. 어느 시점에서 포인터 A와 B가 동일하면 루프가 있습니다. 이 접근법의 문제점은 루프 주위를 두 번 움직일 수 있지만 포인터 A를 사용하면 두 번 이상 움직일 수 있다는 것입니다.

실제로 두 개의 포인터를 가리키는 요소를 찾으려면 더 어렵습니다. 나는 사지에서 나가서 링크 된 목록을 여러 번 반복하지 않는 한 두 개의 포인터로 만하는 것이 불가능하다고 말합니다.

더 많은 메모리로 그것을 수행하는 가장 효율적인 방법은 포인터를 요소에 넣고 배열에 넣고 정렬 한 다음 반복을 찾는 것입니다.

Answer 2

1 단계: 일반적인 방식으로 진행하면 루프를 찾는 데 사용됩니다. 즉, 두 개의 포인터가 있는데, 한 단계에서 하나를 증가시키고 다른 하나는 두 단계로, 둘 다 언젠가 만나면 루프가 있습니다.

2 단계: 하나의 포인터가 어디에 있는지 동결하고 한 단계로 다른 포인터를 늘리고, 다시 만나면 다시 만나면 카운트는 루프의 길이를 제공합니다 (이것은 원형 링크에서 요소 수를 계산하는 것과 동일합니다. 목록).

3 단계 : 두 포인터를 링크 목록의 시작으로 재설정하고 루프 시간의 길이에 대한 하나의 포인터를 증가시킨 다음 두 번째 포인터를 시작하십시오. 두 포인터를 한 단계로 늘리고 다시 만나면 루프의 시작이 될 것입니다 (이것은 N을 찾는 것과 동일합니다.^th 링크 목록의 끝에서 요소).

Answer 3

수학적 증거 + 솔루션

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

간단한 경우 : k <n

포인터 'P'가 시작 루프에있을 때 (즉, 'K'단계를 여행했을 것입니다) Q는 '2K'단계를 여행했을 것입니다. 따라서 효과적으로 Q는 P가 루프에 들어가면 P에서 '2k-k = k'단계보다 앞서 있으며, 따라서 Q는 지금 시작 루프 뒤에 'nk'단계입니다.

P가 시작 Loop에서 만나기 위해 이동했을 때 'MK'단계를 여행했을 것입니다. 그 당시 Q는 '2 (mk)'단계를 여행했을 것입니다. 그러나 그들이 만나고 Q가 시작한 이후, 'NK'단계를 시작하여 'NK'단계를 시작 했으므로 효과적으로 '2 (mk) - (nk)'는 '(mk)'와 같아야합니다.

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

즉, P와 Q는 루프의 단계 수 (또는 일반적으로 언급 된 경우 참조)와 동일한 지점에서 만나는 것을 의미합니다. 이제 MeetPoint에서 p와 q는 모두 'n- (mk)'단계, 즉 'k'단계는 n = m을 보았을 때 뒤에 있습니다. 따라서 헤더에서 P를 다시 시작하면 MeetPoint에서 Q를 시작하지만 이번에는 P, P, Q와 같은 속도로 시작하여 시작 Loop에서만 회의됩니다.

일반적인 경우 : k = nx + y, y <n(따라서 k%n = y)

포인터 'P'가 시작 루프에있을 때 (즉, 'K'단계를 여행했을 것입니다) Q는 '2K'단계를 여행했을 것입니다. 따라서 효과적으로 Q는 P가 루프에 들어가면 P에서 '2K-k = k'단계보다 앞서 있습니다. 그러나 'k'는 'n'보다 크다는 점에 유의하십시오. 즉, Q는 여러 라운드를 루프로 만들었을 것입니다. 따라서 효과적으로 Q는 'N- (K%N)'단계입니다.

P가 처음 Loop에서 MeetPoint로 이동했을 때 'MK'단계를 여행했을 것입니다. (따라서 효과적으로 MeetPoint는 '(mk)%n'단계에있을 것입니다.) 그 당시 Q는 '2 (mk)'단계를 여행했을 것입니다. 그러나 그들이 만나고 Q가 시작된 이래로 'n- (k%n)'단계를 시작하여 시작 루프 뒤의 단계를 시작했습니다. 따라서 효과적으로 Q의 새로운 위치 (2 (mk) - (nk/%n))%n '시작 Loop에서)은 P의 새로운 위치와 같아야합니다 ('(mk)%n '은 시작 루프에서).

그래서,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Answer 4

먼저 우리가 하려고 찾아가,루프에서 또는 목록하지 않습니다.는 경우 루프는 존재한다면 우리를 찾으려고 밖으로의 시작점이다.이를 위해 우리가 사용하는 두 개의 포인터를 즉 slowPtr 및 fastPtr.에서 처음 검출(확인에 대한 반복),fastPtr 움직이 두 가지 단계를 한 번에 있지만 slowPtr 움직임에 의해 한 단계 앞으로 한다.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

그것은 분명이 있는 경우 루프 목록에서 다음 그들을 만나 포인트(7 포인트에 위의 이미지)기 때문에,fastPtr 포인터가 두 번 실행보다 더 빨리 다른 하나입니다.

지금,우리는 두 번째의 문제를 찾는 것의 시작점이다.

가정하고,그들이 만나는 지점에서 7(로에 언급된 위의 이미지).그런 다음,slowPtr 의 루프와 의미에서의 시작을 의미 지점에서 1fastPtr 여전히 회의에서 점(point7).이제 우리는 모두 비교 포인터 값을 경우,그들은 같은 다음의 시작점을 반복 그렇지 않으면 우리는 이 단계에서 앞서(여기에 fastPtr 도에 의해 움직이는 하나의 단계는 각각 시간)과 비교할 때까지 다시 우리를 찾을 동일한 지점입니다.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

이제 하나의 문제는 오는 마음에서,그것은 어떻게 가능합니다.그래서 거기에 좋은 수학적 증거입니다.

가정:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

더 여기에 세부 사항

Answer 5

루프를 찾는 데 사용할 수있는 일반적인 방법으로 진행하십시오. 즉. 두 개의 포인터, 단일 단계에서 하나를 증가시키고 (느린 포인터) 두 단계 (빠른 포인터)로 두 단계를 획득하십시오. 둘 다 언젠가 만나면 루프가 있습니다.

당신이 이미 회의 지점이 루프 헤드 앞에서 k 단계라는 것을 이미 깨달았을 것입니다.

여기서 k는 목록의 비 루프 부분의 크기입니다.

이제 루프 헤드로 천천히 움직입니다

충돌 지점에서 빠르게 유지하십시오

그들 각각은 루프 시작에서 k 단계입니다 (루프의 헤드 앞에서 빠른 k 단계 인 목록의 시작부터 느리게 사진을 찍기 위해 그림을 그리십시오).

이제 동일한 속도로 움직입니다. 루프 스타트에서 만나야합니다.

예를 들어

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

Answer 6

링크 된 목록에서 루프의 시작을 찾는 코드입니다.

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Answer 7

링크 목록에서 루프를 찾는 두 가지 방법이 있습니다. 1. 루프가있는 경우 두 개의 포인터 1 단계를 사용하고 다른 두 단계를 사용하십시오. 어느 시점에서 두 포인터는 동일한 값을 얻고 널에 도달하지 않습니다. 그러나 루프 포인터가 한 시점에서 Null에 도달하지 못하고 두 포인터는 동일한 값을 얻지 못합니다. 그러나이 접근법에서는 링크 목록에 루프가 있지만 루프를 정확히 시작하는 곳은 알 수 없습니다. 이것은 효율적인 방법도 아닙니다.

2. 값이 고유 해야하는 방식으로 해시 기능을 사용하십시오. 우리가 예외를 통해 복제를 삽입하려고하는 경우. 그런 다음 각 노드를 통해 주소를 해시로 밀어 넣습니다. 포인터가 NULL에 도달하고 해시에서 예외가 아니라면 링크 목록에 사이클이 없음을 의미합니다. 해시에서 예외를 얻는다면 목록에주기가 있음을 의미하며 이는 사이클이 시작되는 링크입니다.

Answer 8

글쎄, 나는 하나의 포인터를 사용하여 방법을 시도했다 ... 나는 여러 데이터 세트에서 메소드를 시도했다 .... 링크 된 목록의 각 노드에 대한 메모리가 증가하는 순서로 할당되므로 링크 된 목록을 가로 지르면서 링크 된 목록의 헤드, 노드의 주소가 가리키는 노드의 주소보다 커지면 루프의 시작 요소뿐만 아니라 루프가 있는지 확인할 수 있습니다.

Answer 9

내가 찾은 가장 좋은 대답은 여기에있었습니다.
Tianrunhe : 원리-시작 지점-원리-연결된 목록

• 'm'은 머리와 start_loop 사이의 거리입니다
• 'l'루프 길이입니다
• 'd'는 meeting_point와 start_loop 사이의 거리입니다

• P1 v에서 이동하고 P2가 2*V에서 이동

  2 개의 포인터가 만나면 : 거리 실행은 = m+ n*l -d = 2*(m+ l -d)

  => 이는 P1이 Head에서 시작하고 P2가 Meeting_point에서 시작하고 같은 속도로 이동하면 @ start_loop를 만날 것임을 의미합니다 (여기서 수학적이 아님).

Answer 10

인용하다 이것 포괄적 인 답변 링크.

Answer 11

1. 루프를 찾는 데 사용할 수있는 일반적인 방법으로 진행하십시오. 즉. 두 개의 포인터를 두 개의 포인터를 두 단계로, 다른 하나는 두 단계로, 둘 다 언젠가 만나면 루프가 있습니다.

2. 포인터 중 하나를 고정 상태로 유지하십시오. 루프의 총 노드 수를 얻으십시오.

3. 이제 루프 의이 시점 (루프의 다음 노드에 대한 두 번째 포인터를 증가) 링크 된 목록을 뒤집고 X.

4. 이제 루프 트래브의 동일한 지점에서 두 번째 포인터 (루프가 깨 졌음)를 사용하여 링크 된 목록을 사용하고 남아있는 노드 수를 계산합니다.

5. 루프는 ((x+y) -l) 2 노드 이후에 시작됩니다. 또는 (((x+y) -l) 2+1) th 노드에서 시작합니다.

Answer 12

1. 루프를 찾는 데 사용할 수있는 일반적인 방법으로 진행하십시오. 즉. 두 개의 포인터를 두 개의 포인터를 두 단계로, 다른 하나는 두 단계로, 둘 다 언젠가 만나면 루프가 있습니다.

2. 포인터 중 하나를 고정 상태로 유지하십시오. 루프의 총 노드 수를 얻으십시오.

3. 이제 루프 의이 시점 (루프의 다음 노드에 대한 두 번째 포인터를 증가) 링크 된 목록을 뒤집고 X.

4. 이제 루프 트래브의 동일한 지점에서 두 번째 포인터 (루프가 깨 졌음)를 사용하여 링크 된 목록을 사용하고 남아있는 노드 수를 계산합니다.

5. 루프는 ((x+y) -l) 2 노드 이후에 시작됩니다. 또는 (((x+y) -l) 2+1) th 노드에서 시작합니다.

Answer 13

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

Answer 14

1. 루프를 감지하십시오
2. 각 요소의 주소를 세트로 복사하십시오. 중복이 발견되면 루프의 시작입니다.