idea：对于有环结构的链表，判断环结点位置，开始想到遍历链表，直到某一个结点出现第二遍，所以要进行比对的过程，想到前面学到利用哈希表解决相交链表，可以在这使用。不过对于为什么使用_set不太清楚，哈希表的操作及原理下来也要好好补一下
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { unordered_set<ListNode*> hash; //创建哈希表 while(head!=NULL){ //判断是否有环结构 if(hash.count(head)) //与已有元素进行比对 return head; hash.insert(head); //录入哈希表 head=head->next; } return NULL; } }
复杂度分析
时间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
空间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
进阶：双指针。 idea：具体是用快慢指针相遇问题，通过数学计算来解决问题，具体算法如下
代码实现：
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast=head, *slow=head, *p=head; while(fast!=NULL && fast->next!=NULL && fast->next->next!=NULL){ fast=fast->next->next; slow=slow->next; if(fast==slow){ while(p!=slow){ p=p->next; slow=slow->next; } return p; } } return NULL; } };
复杂度分析
时间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。在最初判断快慢指针是否相遇时，\textit{slow}slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)O(N)+O(N)=O(N)。
空间复杂度：O(1)O(1)。我们只使用了 \textit{slow}, \textit{fast}, \textit{ptr}slow,fast,ptr 三个指针。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。