判断单链表是否有环，设一快一慢两个指针，快指针每次前进两个节点，慢指针每次前进一个节点，如果两个指针可以相遇，则有环
python版
1 #141
2 #Runtime: 57 ms (Beats 75.48%)
3 #Memory: 20.6 MB (Beats 48.63%)
4
5 # Definition for singly-linked list.
6 # class ListNode:
7 # def __init__(self, x):
8 # self.val = x
9 # self.next = None
10
11 class Solution:
12 def hasCycle(self, head: Optional[ListNode]) -> bool:
13 slow, fast = head, head
14 while slow and fast and fast.next:
15 fast = fast.next.next
16 slow = slow.next
17 if slow == fast:
18 return True
19 return False
C++版
1 //141
2 //Runtime: 80 ms (Beats 6.2%)
3 //Memory: N/A (Beats N/A)
4
5 /**
6 * Definition for singly-linked list.
7 * struct ListNode {
8 * int val;
9 * ListNode *next;
10 * ListNode(int x) : val(x), next(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 bool hasCycle(ListNode *head) {
16 ListNode *slow = head, *fast = head;
17 while(fast && fast->next) {
18 slow = slow->next;
19 fast = fast->next->next;
20 if(slow == fast) break;
21 }
22 if(fast == NULL || fast->next == NULL) return false;
23 return true;
24 }
25 };