Linked List Cycle

141. Linked List Cycle

https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212/

Explore - LeetCode

 

Language: C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next) { // slow && fast
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast)
                return true;
        }
        
        return false;
    }
};

 

솔루션의 접근방법은 두 가지이다.

1) hash table 사용하는 방법이 있고 :   Time, Space : O(n)

2) Floyd's Cycle Finding Algorithm (= Floyd's Tortoise and Hare) 이 있다. : Time : O(n), Space : O(1)

설명 부분에서 hash table 보다 더 나은 방식이 있다, 빨리 방문하는 포인터와 천천히 방문하는 포인터가 있고 

빨리 방문하는 포인터는 2개씩 넘어가고 천천히 방문하는 포인터는 1개씩 넘어가면 된다고 설명이 있었다.

위의 코드는 2) 해결법이다.

(현재 문제설명부분 말고 바로 전 설명 부분에 있다: https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1211/)