링크 고전 문제 집계

링크 에서 흔히 볼 수 있 는 면접 문 제 를 수집 했다.
1. 단일 체인 표 에 고리 가 있 는 지 어떻게 판단 합 니까?
2. 하나의 고리 의 입구 점 이 어디 에 있 는 지 어떻게 판단 합 니까?
3. 링 의 길 이 를 어떻게 압 니까?
4. 두 개의 단일 체인 표 (고리 없 음) 가 교차 하 는 지 어떻게 압 니까?
5. 만약 에 두 개의 단일 체인 표 (고리 없 음) 가 교차 하면 그들 이 교차 하 는 첫 번 째 노드 가 무엇 인지 어떻게 알 수 있 습 니까?
6. 두 개의 단일 체인 표 (고리 가 있 음) 가 교차 하 는 지 어떻게 압 니까?
7. 만약 에 두 개의 단일 체인 표 (고리 가 있 음) 가 교차 하면 그들 이 교차 하 는 첫 번 째 노드 가 무엇 인지 어떻게 알 수 있 습 니까?
1. 빠 르 고 느 린 걸음 으로 길 게 걷는다.두 포인터 p 와 q 를 각각 머리 결점 을 가리 키 게 합 니 다. p 는 매번 앞으로 나 아 갑 니 다. q 는 매번 두 걸음 씩 전진 합 니 다. 만약 p 와 q 가 겹 칠 수 있다 면 링 이 있 습 니 다.이렇게 이해 할 수 있 습 니 다. 이런 방법 은 p 가 움 직 이지 않 는 것 과 같 습 니 다. q 가 한 걸음 더 나 아 갈 때마다 모든 것 이 p 를 따라 잡 을 때 가 있 습 니 다.
우 리 는 포인터 p 와 q 가 각각 속도 로 1 과 2 로 전진 하 는 것 을 알 았 다.다른 속도 로 가면 되 나 요?
p 와 q 가 각각 속도 로 v1 과 v2 로 전진한다 고 가정 합 니 다.링 이 있 으 면 포인터 p 와 q 를 설정 하여 링 에 처음 들 어 갈 때 그들 은 링 의 첫 번 째 노드 에 비해 각각 a 와 b (오프셋 주 소 를 노드 개수 로 이해 할 수 있 습 니 다)
이 를 통 해 알 수 있 듯 이 링크 에 고리 가 있 는 충전 조건 은 바로 특정한 순환 일 때 포인터 p 와 q 의 값 이 같 고 바로 이들 이 상대 적 으로 링 중의 첫 번 째 노드 의 오프셋 이 같다 는 것 이다.우 리 는 링 의 결점 개 수 를 n 으로 설정 하고 프로그램 은 m 회 순환 했다.
이 를 통 해 다음 과 같은 식 으로 성립 될 수 있다. (mod (n) 즉 n 에 대한 나머지)
(a+m*v1)mod(n) = (b+m*v2) mod(n)
등식 왼쪽 mod (n) 의 최대 정 수 는 k1 이 고 등식 오른쪽 mod (n) 의 최대 정 수 는 k2 이다.
(a+m*v1)-k1*n = (b+m*v2)-k2*n
이상 등식 정리:
m= |((k2-k1)*n+a-b)/( v2-v1)|       ①
등식 ① 이 성립 되면 순환 횟수 m 를 정수 로 해 야 한다.분명히 v2 - v1 이 1 이면 등식 이 성립 된다.
이렇게 하면 p 와 q 는 각각 속도 가 v1 과 v2 이 고 | v2 - v1 | 이 1 일 때 상기 알고리즘 을 누 르 면 링크 에 고리 가 있 는 지 찾 을 수 있 습 니 다.물론 | v2 - v1 | 1 이 아 닐 때 조건 에 맞 는 m 를 얻 을 수 있 습 니 다.

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

시간 복잡 도 분석: 차 미 (링 밖 에 있 음) 의 길 이 는 len1 (결점 개수) 이 고 링 안의 길 이 는 len2 이 며 링크 의 총 길 이 는 n 이 라면 n = len1 + len2 이다. 。p 의 길이 가 1 이 고 q 의 길이 가 2 일 때 p 포인터 가 링 입구 에 도착 하 는 데 len1 시간 이 필요 합 니 다. p 가 입구 에 도착 한 후에 q 가 어디 에 있 는 지 확실 하지 않 지만 링 안에 있 을 것 입 니 다. 이때 p 와 q 가 따라 잡기 시 작 했 습 니 다. q 는 최 장 len2 시간 이면 p (p 와 q 가 모두 링 입 구 를 가리 키 는 것) 를 따라 잡 을 수 있 습 니 다. 최 단 1 걸음 이면 p (p 가 링 입 구 를 가리 키 고 q 가 링 입구 의 앞 노드 를 가리 키 는 것) 를 따라 잡 을 수 있 습 니 다.사실 한 걸음 을 지나 갈 때마다 q 와 p 의 거 리 는 한 걸음 가 까 워 지기 때문에 q 와 p 의 거 리 를 지나 면 p 를 따라 잡 을 수 있 습 니 다.따라서 총 시간 복잡 도 는 O (n) 이 고 n 은 링크 의 총 길이 이다.
2. 체인 헤드 와 충돌 점 에서 한 걸음 한 걸음 씩 스 캔 하여 충돌 할 때 까지 이 충돌 점 은 바로 링 의 입구 이다.
증명 은 다음 과 같다.
링크 모양 은 숫자 6 과 유사 합 니 다. 
차 미 (링 밖 에 있 음) 길이 가 a (결점 개수) 이 고 링 안의 길 이 는 b 라 고 가정 합 니 다. 
총 길이 (총 점) 는 a + b 입 니 다. 
처음부터 0 base 번호.
i 단계 방문 의 결산 점 을 S (i) 로 표시 합 니 다.i = 0, 1 ... 
i ＜ a 일 경우 S (i) = i; 
i ≥ a 시 S (i) = a + (i - a)% b.
추적 과정 을 분석 하 다. 
두 바늘 이 각각 앞으로 나 아가 x 보 를 거 친 후에 부 딪 힌 다 고 가정 한다.S (x) = S (2x) 
링 의 주기성 은 2x = tb + x 이다.받다 
또한 부 딪 힐 때 는 반드시 링 안에 있어 야 하 며, 꼬리 부분 에 있 을 수 없고, x > = a 가 있어 야 한다.
연결 점 은 출발점 에서 a 단계, 즉 S (a) 입 니 다. 
S(a) = S(tb+a) = S(x+a)。 
결론: 충돌 점 x 에서 a 단계 로 전진 하 는 것 이 바로 연결 점 이다.
가설 에 따 르 면 S (a - 1) 는 끝 부분 에 있 고 S (a) 는 고리 에 있 으 며 S (x + a) 는 반드시 고리 에 있다.부 딪 힐 수 있 습 니 다. 
그리고 같은 전진 a 보, 같은 연결 점 이기 때문에 반드시 충돌 이 발생 한다.
종합 적 으로 x 점 과 출발점 에서 동시에 전진 하 는데 첫 번 째 충돌 점 은 바로 연결 점 이다.

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

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

    return slow;
}

시간 복잡 도 분석: 차 미 (링 밖 에 있 음) 의 길 이 는 len1 (결점 개수) 이 고 링 안의 길 이 는 len2 라 고 가정 한다.시간 복잡 도 는 '링 이 존재 하 는 시간 복잡 도' + O (len1) 이다.
3. 충돌 점 부터 두 개의 포인터 p 와 q, q 는 한 걸음 으로 전진 하고 q 는 두 걸음 으로 전진 하 며 다음 충돌 이 거 친 조작 횟수 는 바로 링 의 길이 입 니 다.이것 은 이해 하기 쉽다. 예 를 들 어 두 운동선수 A 와 B 가 출발점 에서 달리 기 를 시작 하면 A 의 속 도 는 B 의 두 배 이다. A 가 한 바퀴 를 돌 때 B 는 마침 두 바퀴 를 완 주 했 고 A 와 B 는 동시에 출발점 에 있다.이때 A 달리기 의 길 이 는 링 의 길이 에 해당 한다.
차 미 (링 밖) 길이 가 len1 (결점 개수) 이 고 링 안의 길이 가 len2 라 고 가정 하면 시간 복잡 도 는 '링 이 존재 하 는 시간 복잡 도' + O (len2) 이다.
4. 법 1: 링크 A 의 꼬리 노드 의 next 지침 을 링크 B 의 머리 결 점 을 가리 키 고 새로운 링크 를 구성 했다.문 제 는 이 새 링크 에 고리 가 있 는 지 를 구 하 는 문제 로 바 뀌 었 다.
     시간 복잡 도 는 링 이 존재 하 는 지 의 시간 복잡 도, 즉 O (length (A) + length (B)) 로 두 개의 추가 지침 을 사용 했다.
     법 2: 두 개의 링크 가 교차 하면 교차 하 는 노드 부터 그 후의 모든 노드 는 두 개의 링크 가 공유 하 는 것 이다.따라서 그들 이 교차 하면 마지막 노드 는 반드시 공유 할 것 이다.따라서 두 링크 가 교차 하 는 것 을 판단 하 는 방법 은 첫 번 째 링크 를 옮 겨 다 니 며 마지막 노드 를 기억 하 는 것 이다.그 다음 에 두 번 째 링크 를 옮 겨 다 니 며 마지막 노드 에 이 르 렀 을 때 첫 번 째 링크 의 마지막 노드 와 비교 하고 똑 같 으 면 교차 합 니 다.
     시간 복잡 도: O (length (A) + length (B)), 하지만 마지막 노드 만 추가 포인터 로 저장 합 니 다.
5. 링크 A 의 꼬리 노드 의 next 지침 을 링크 B 의 머리 결 점 을 가리 키 고 고 리 를 구성 했다.문 제 는 이 고 리 를 구 하 는 입구 문제 로 바 뀌 었 다.시간 복잡 도: 고리 입구 의 시간 복잡 도 구하 기
6. 두 개의 링크 A, B 에 고리 가 있 는 지 판단 한다. (주, 두 개의 링크 가 교차 하 는 것 은 이 링 이 두 개의 링크 에 속 하 는 것 을 말한다)
만약 고리 가 하나 밖 에 없다 면 A, B 는 교차 할 수 없다.
만약 에 둘 다 고리 가 있 으 면 A 의 고리 입 구 를 구하 여 B 링크 에 있 는 지 판단 하고 있 으 면 A, B 가 교차 하 는 지 설명 한다.
시간 복잡 도: "링 입구 문제 의 시간 복잡 도" + O (length (B))
7. 각각 두 개의 링크 A, B 의 길이 LA 와 LB (링 의 길이 와 링 이 입구 점 까지 의 길이 의 합 이 바로 링크 길이) 를 계산 하고 문제 3 을 참조 합 니 다.
만약 에 LA > LB 라면 링크 A 포인터 가 먼저 LA - LB 가 고 링크 B 포인터 가 다시 걸 어가 면 두 포인터 가 만 나 는 위 치 는 바로 교차 하 는 첫 번 째 노드 이다.
LB > LA 가 있 으 면 링크 B 포인터 가 먼저 LB - LA 가 고 링크 A 포인터 가 다시 걷 기 시작 하면 두 포인터 가 만 나 는 위 치 는 바로 교차 하 는 첫 번 째 노드 이다.
시간 복잡 도: O (max (LA, LB))