# 141-Linked List Cycle
###### tags: `Easy`
## Question
https://leetcode.com/problems/linked-list-cycle/


## Key
- 想法:這題有點數學...想到國小數學，A跟B賽跑，多久之後快的會追上慢的，所以就是用快慢算子不停迭代Next node直到追上為止，如果過程中出現NULL代表沒有loop
- 另一個想法是因為題目有限制list長度，所以迭代到最大長度次數沒出現NULL的話，有Cycle存在

## Solution
### c++

class Solution {
public:
    bool hasCycle(ListNode *head) {
	
		// if head is NULL then return false;
        if(head == NULL)
            return false;
        
		// making two pointers fast and slow and assignning them to head
        ListNode *fast = head;
        ListNode *slow = head;
        
		// till fast and fast-> next not reaches NULL
		// we will increment fast by 2 step and slow by 1 step
        while(fast != NULL && fast ->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            
			
			// At the point if fast and slow are at same address
			// this means linked list has a cycle in it.
            if(fast == slow)
                return true;
        }
        
		// if traversal reaches to NULL this means no cycle.
        return false;
    }
};

### python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        maxi=10**4+10
        count=0
        temp=head

        while temp!=None and count<maxi:
            count+=1
            temp=temp.next

        if count==maxi:
            return True
        else:
            return False