Linked List Cycle II

142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/

Linked List Cycle II - LeetCode

Language: C++

/**
 * 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;
        
        ListNode* fast = head;
        ListNode* slow = head;
        
        
        while (fast && fast->next) {
            
            fast = fast->next->next;
            slow = slow->next;
            
            if (fast == slow)
                break;
            
        }
        
        if (fast == slow) {
            
            slow = head;
            
             while (fast != slow) {
            
                fast = fast->next;
                slow = slow->next;
                 
            }
            return fast;
            
        } else
            return nullptr;
    }
};

어제는 하루 쉬었고, 그저께 I 버전을 풀었을 때 fast, slow 노드를 가지고 fast 는 2개씩, slow 는 1개씩 이동하면서 같은 노드일 경우 값을 리턴하도록 했어서 비슷하게 하면 되지 않을까 했었다. 이 문제는 cycle의 시작점을 찾는 것이었다. 

두 가지 솔루션이 있었다.

1) hash 사용

2) Floyd's Tortoise and Hare

hash 는 방문 여부를 표시해놓으면서 검색하면 되므로 넘어갔고, 플로이드의 토끼와 거북이 알고리즘을 보았다.

fast는 2개씩, slow는 1개의 노드를 이동하면서 같을 때를 찾고, slow를 다시 시작점으로 보내서 둘 다 1개의 노드만 이동하면서 같은 것을 찾았을 때가 시작점이라는 알고리즘이다.

 

 

References

https://fierycoding.tistory.com/45

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬