环形链表
判断一个链表中是否有环，如果有返回环的起始位置。难点有两个，一是判断是否有环，二是找到起始点。这里有两种方法，一种是哈希集，另一种是快慢指针。
对应题目142. 环形链表 II??️
哈希集
从头开始遍历整个链表，并使用哈希集去保存每个节点，接着判断节点是否有重复的。如果有那么这就是环的起始节点。分析复杂度，需要遍历整个链表所以时间复杂度为\(O(N)\)；使用了哈希集去保存节点所以空间复杂度为\(O(N)\)。
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> mySet;
while(head != nullptr) {
if(mySet.count(head) == 0) {
mySet.insert(head);
head = head->next;
}else {
return head;
}
}
return nullptr;
}
快慢指针
定义两个指针，一快一慢，快指针每次移动两步，慢指针每次移动一步。如果链表有环，那么最终快慢指针会相遇。相遇后再从头节点head开始每次移动一步的速度遍历，慢指针也是如此。最终head与慢指针相遇的地方即为环的起始点。分析复杂度，对于时间复杂度，慢指针至少会遍历一次整个链表，所以时间复杂度为\(O(N)\)；而没有像哈希集一样定义其他数据结构，因此空间复杂度为\(O(1)\)。
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(slow == fast) {
while(slow != head) {
slow = slow->next;
head = head->next;
}
return head;
}
}
return NULL;
}