링크 에 고리 가 있 는 지 판단 하 는 세 가지 사고

질문
링크 를 지정 하여 링크 에 고리 가 있 는 지 판단 합 니 다.주: 이 고 리 는 끝 노드 가 앞의 임의의 노드 에 연 결 될 수 있 습 니 다.
0x 02. 세 가지 방법 분석
첫 번 째: 해시 시계
가장 쉽게 생각 나 는 것 은 하나의 노드 를 만 날 때마다 존재 하지 않 으 면 해시 표 에 저장 하고 존재 하면 바로 돌아 가 는 것 이다 true.중복 되 는 것 이 하나 도 없다 false.
주의:

은 unordered_set 대신 set 사용 하 는 것 이 좋 고 시간 을 절약 하 는 것 이 좋다.

저 장 된 데이터 형식 은 반드시 지침 이 어야 합 니 다. 값 이 같 을 수 있 기 때 문 입 니 다.

우열 세 분석:

공간 교환 시간 은 순서대로 옮 겨 다 니 지만 링크 의 공간 을 하나 더 사용 했다.

시간의 복잡 도 는 다음 과 같다. O（N）

공간의 복잡 도 는 다음 과 같다. O（N）

두 번 째: 빠 르 고 느 린 두 바늘
환상 트랙 에서 달리 면 빠 른 사람과 느 린 사람 이 반드시 만 나 는 것 은 상식 이다.그래서 우 리 는 빠 른 지침 을 사용 할 수 있 습 니 다. 매번 두 걸음 씩 걷 고 느 린 지침 을 사용 할 수 있 습 니 다. 매번 한 걸음 씩 걷 고 고리 가 존재 하면 반드시 만 날 수 있 습 니 다. 빠 른 지침 이 비어 있 으 면 고리 가 없다 는 것 을 설명 합 니 다.
주의:

초기 화 할 때 빠 른 지침 은 head->next 일 것 입 니 다.

우열 세 분석:

시간 으로 공간 을 바 꾸 지만 시간 소모 도 많 지 않 고 링 에 들 어 갈 때 교체 횟수 가 많 습 니 다.

시간 복잡 도: O（N+K）, K 는 링 의 길이 이다.

공간 복잡 도: O（1）.별도의 공간 을 사용 하지 않 았 습 니 다.

추가: 링 이 되 어 있 는 노드 로 돌아 가 려 면 빠 른 포인터 가 만 나 는 점 을 찾 아야 합 니 다. 포인터 p 로 대체 한 다음 에 포인터 로 머리 를 가리 키 는 지침 을 사용 합 니 다. q 로 대체 하고 매번 에 한 걸음 씩 옮 겨 서 그들 이 만 날 때 까지 그들 이 만 나 는 점 은 링 의 입구 입 니 다!수학 적 증명 을 생략 하 는 것 도 플 로 이 드 알고리즘 의 응용 이다.
세 번 째: 표지 법
우 리 는 모든 방문 변수 에 표 시 를 할 수 있 습 니 다. 만약 다음 에 도 이 표 시 를 발견 하면 설명 은 반드시 고리 가 될 것 입 니 다.
흔히 볼 수 있 는 가격 표시 법 은 자신의 가 치 를 바 꾸 는 것 으로 보통 큰 숫자 로 일반적으로 얻 을 수 없 는 가 치 를 나타 낸다. 물론 이런 방법 은 엄격 한 의미 에서 엄밀 하지 않다 고 할 수 있다.
또한 모든 방문 한 노드 를 head 노드 로 가리 킬 수 있다. 의 미 는 지침 을 강제로 바 꾸 는 것 이 고 지침 을 특정한 주소 로 바 꿀 수도 있다. 한 마디 로 하면 원래 의 노드 를 상징적 인 의미 로 바 꿀 수 있다 면.
주의:

값 을 바 꾸 는 것 은 엄격 한 의미 에서 잘못된 것 이지 만 보통 가능 하 다. 우 리 는 비교적 큰 숫자 로 바 꿀 수 있다.

지침 을 바 꾸 는 사상 은 충분히 사용 할 수 있다.

우열 세 분석:

이런 방법의 가장 큰 단점 은 바로 원래 의 링크 구 조 를 바 꾸 는 것 이다. 의미 가 크 지 않 고 보통 고리 가 되 는 지 판단 하기 위해 만 사용한다. 그렇지 않 으 면 링크 구조 가 바 뀌 는 것 은 거 스 를 수 없 기 때문에 이 링크 는 사용 할 수 없다.

시간 복잡 도: O（N）.

O（1） 。

해결 코드 – 해시 표

bool hasCycle(ListNode *head) {
   unordered_set<ListNode*> map;
   while(head){
       if(map.count(head)) return true;
       else map.insert(head);
       head=head->next;
   }
   return false;
 }
 

0x 04. 해결 코드 – 속도 더 블 포인터

bool hasCycle(ListNode *head) {
    if(!head||!head->next) return false;
    ListNode*slow=head;
    ListNode*fast=head->next;
    while(slow!=fast){
        if(!fast||!fast->next) return false;
        slow=slow->next;
        fast=fast->next->next;
    }
    return true;
}

해결 코드 – 표지 법

bool hasCycle(ListNode *head) {
   int flag=1e6;
   while(head){
       if(head->val==flag) return true;
       else head->val=flag;
       head=head->next;
   }
   return false;
}

ATFWUS --Writing By 2020–03–24