C++LeetCode(142.단일 체인 표 의 링 2)실현

[LeetCode]142.Linked List Cycle II 싱글 체인 시트 의 링 2
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow up:
Can you solve it without using extra space?
이 구 단 사슬 표 중의 고리 의 시작 점 은 이전에 단 사슬 표 에 고리 의 연장 이 있 는 지 판단 하 는 것 이 며,이전의 그 길 을 참조 할 수 있다.  Linked List Cycle 。여 기 는 역시 빠 르 고 느 린 지침 을 설치 해 야 한다.그러나 이번 에는 두 지침 이 만 나 는 위 치 를 기록 해 야 한다.두 지침 이 만 나 면 그 중의 한 지침 을 체인 표 머리 에서 시작 하여 한 걸음 두 걸음 한 걸음 마치 앞니 와 같 고 마귀 의 걸음 과 같다.하하,그만 해 그만 해...이때 다시 만 나 는 위 치 는 바로 링크 의 시작 위치 입 니 다.왜 그 럴 까요?여기 에는 뜨 거 운 네티즌'나 는 새 가 날 고 싶 어한 다.'의 설명 을 직접 붙 여 놓 았 습 니 다.빠 른 지침 은 매번 2 번 가 고 느 린 지침 은 매번 1 번 가 며 빠 른 지침 은 느 린 지침 의 두 배 이기 때 문 입 니 다.빠 른 바늘 은 느 린 바늘 보다 한 바퀴 더 돌 았 다.그래서 헤드 에서 링 까지 의 출발점+링 의 출발점 에서 그들 이 만 나 는 점 까지 의 거 리 는 링 한 바퀴 의 거리 와 같다.이제 다시 시작 하면 헤드 가 링 기점 까지 운행 하 는 것 과 만 남 점 에서 링 기점 까지 의 거리 도 같다.그들 은 링 의 출발점 에서 그들 이 만 나 는 점 까지 의 거 리 를 동시에 줄 인 셈 이다.코드 는 다음 과 같 습 니 다:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        if (!fast || !fast->next) return NULL;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/142
유사 한 제목:
Linked List Cycle
Find the Duplicate Number
참고 자료:
https://leetcode.com/problems/linked-list-cycle-ii/
https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything
여기 서 C++구현 LeetCode(142.싱글 체인 시트 의 링 2)에 관 한 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 싱글 체인 시트 의 링 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!