leetcode 142 링 링크 의 시작 점 찾기

제목.
4. 567917. 링크 를 지정 하고 링크 가 링 에 들 어가 기 시작 하 는 첫 번 째 노드 를 되 돌려 줍 니 다.링크 에 고리 가 없 으 면 null 로 돌아 갑 니 다
4. 567917. 설명: 주어진 링크 를 수정 할 수 없습니다
가 급 적 추가 저장 공간 을 사용 하지 않 는 다.
분석 하 다.
4. 567917. 이것 은 고 리 를 찾 는 문제 와 비슷 하지만 난이도 가 증가 했다.많은 시간 을 들 여 했다
4. 567917. 빠 른 지침 을 이용 하여 고리 가 있 는 지 없 는 지 를 찾 는 것 이 분명 하 다.그림 을 그 려 보 니 느 린 지침 이 가 는 걸음 수 는 링 의 길이 인 것 으로 나 타 났 다.그래서 다른 지침 이 처음부터 출발 하면 느 린 지침 이 계속 앞으로 가면 그들 이 만 나 는 노드 는 바로 링 의 입구 이다
4. 567917. 1 판 코드 는 기록 길이 의 정형 을 사용 하여 절 차 를 더 밟 았 다.뒤에 최적화 됐어 요
코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //     ，       ，                 ，           ，         。
        if((head == nullptr) || (head->next == nullptr)){
            return nullptr;
        }
        int count = 0;
        ListNode* normal = head;
        ListNode* fast = head;
        //             
        while(true){
            if((fast->next == nullptr) || (fast->next->next == nullptr)){
                return nullptr;
            }
            fast = (fast->next)->next;
            normal = normal->next;
            count += 1;
            if(fast == normal){
                break;
            }
        }
        // count         
        fast = head;
        while(count > 0){
            fast = fast->next;
            count--;
        }
        normal = head;
        while(true){
            if(normal == fast){
                return fast;
            }
            fast = fast->next;
            normal = normal->next;
        }
    }
};

개량 버 전 코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //     ，       ，                 ，           ，         。
        if((head == nullptr) || (head->next == nullptr)){
            return nullptr;
        }
        // int count = 0;
        ListNode* normal = head;
        ListNode* fast = head;
        //             
        while(true){
            if((fast->next == nullptr) || (fast->next->next == nullptr)){
                return nullptr;
            }
            fast = (fast->next)->next;
            normal = normal->next;
            // count += 1;
            if(fast == normal){
                break;
            }
        }
        // count         
        fast = head;
        // while(count > 0){
        //     fast = fast->next;
        //     count--;
        // }
        while(true){
            if(normal == fast){
                return fast;
            }
            fast = fast->next;
            normal = normal->next;
        }
    }
};

총결산
링크 문 제 는 역시 빠 르 고 느 린 지침 의 응용 과 그림 을 그 리 는 것 을 중시 해 야 한다.