判斷單鏈表是否有環(huán)，設(shè)一快一慢兩個(gè)指針，快指針每次前進(jìn)兩個(gè)節(jié)點(diǎn)，慢指針每次前進(jìn)一個(gè)節(jié)點(diǎn)，如果兩個(gè)指針可以相遇，則有環(huán)
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 };