###### tags: `Leetcode` `easy` `list` `pointer` `python` `c++` `Top 100 Liked Questions`

# 141. Linked List Cycle

## [題目出處] https://leetcode.com/problems/linked-list-cycle/

## 題目:
Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. **Note that pos is not passed as a parameter.**

Return true if there is a cycle in the linked list. Otherwise, return false.

**Follow up: Can you solve it using O(1) (i.e. constant) memory?**


## 解題思考:
* 龜兔賽跑!!
* 兩個pointer slow、fast
* slow每次走一步、fast每次走兩步
* 若fast能追上slow表示有cycle
* [高手詳解:]https://clay-atlas.com/blog/2022/03/08/leetcode-141-linked-list-cycle/

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)
        
#法1 time: O(n) space:O(n)
'''
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        check = []
        current = head
        while current:
            if current in check:
                return True
            check.append(current)
            current = current.next
        return False
'''
#法2 time: O(n) space: O(1)   
class Solution(object):
    def hasCycle(self, head):  
        #龜兔賽跑
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
            
        
if __name__ == '__main__':
    head=ListNode(3)
    head.insert(2)
    head.insert(0)
    head.insert(-4)
    tail=head
    while tail.next:
        tail=tail.next
    tail.next=head.next
    
    result = Solution()
    ans = result.hasCycle(head)
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void InsertNode(ListNode* root, int data){
    ListNode *tail=root;
    if (tail->next != nullptr)
        InsertNode(tail->next,data);
    else{
        ListNode *new_node= new ListNode(data);
        tail->next=new_node;
    }
}

void PrintList(ListNode* root){
    ListNode *tail=root;
    vector<int> res;
    int counter=0;
    while (tail!=nullptr){
        res.push_back(tail->val);
        tail=tail->next;
        counter+=1;
        if (counter>10)
            break;
    }
    cout<<"PrintList:";
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

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

int main(){
    ListNode *head=new ListNode(3);
    InsertNode(head,2);
    InsertNode(head,0);
    InsertNode(head,-4);
    PrintList(head);
    //create loop:
    ListNode *tail=head;
    while (tail->next!=nullptr){
        tail=tail->next;
    }
    tail->next=head->next;
    cout<<"Loop  ";
    PrintList(head);

    Solution res;
    bool ans=res.hasCycle(head);
    cout<<ans<<endl;

    return 0;
}