题意:
对于一个给定的链表,返回环的入口节点,如果没有环,返回null。
方法:
集合
思路:初始化一个集合;
遍历链表的节点,并向集合中插入该节点。
如果发现集合中已经存在该节点,则说明是环的入口节点。(因为说明是绕了一个环,第二次访问该节点)
class Solution { public: ListNode *detectCycle(ListNode *head) { unordered_set<ListNode*> st;//集合 ListNode *p=head;//初始化 while(p){ if(st.count(p)){//如果集合中存在该节点,则说明是环的入口节点 return p; }else{//否则,插入节点 st.insert(p); } p=p->next; } return nullptr;//不存在环 } };
时间复杂度:空间复杂度: