题目描述
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
算法
(set)
- 如果有环,说明一个节点会遍历2次,那么用set,出现重复元素的时候,就是入口节点
- 插入insert后,要记得向后移,cur = cur->next
- 最后如果没找到,说明没有环,输出NULL。
时间复杂度
$O(n)$
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
unordered_set<ListNode*> us;
if(!head || !head->next) return NULL;
auto cur = head;
while(cur)
{
if(us.count(cur)) return cur;
else us.insert(cur), cur = cur->next; // **1
}
return NULL; // **2
}
};
算法
(双指针)
- 这道题的解题思想已经明白了,犯了几个小错说一下。
- 一开始的while循环条件,之前一直感觉while()的循环条件是
while(first == second)
这一类的,其实可以不是,这道题就是while(first && second)
,表示2个指针非空的时候。因为如果是有环的,就会一直循环下去。 - 我们在一直循环的过程中,找到环的入口,然后直接return答案就好。
- 第二个是将第2个while跟
if(first == second)
写成了平行,其实这样错了。因为逻辑是先first走1步,second走2步,相遇的时候再second走1步。如果不把第2个while写到if里面,那么就不能实现前面的逻辑了。 - 然后second的一开始走两步,我第一次写成了
second = second->next->next
,其实这样不对,如果second->next == NULL
,这么写会报错,所以先second->next
走一步,如果下一步存在if(second)
,就再走一步。如果不存在,直接return NULL
,因为这样也说明该链表不存在 环,有环是不会为空的。
时间复杂度
$O(n)$
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(!head || !head->next) return NULL;
ListNode *first = head;
ListNode *second = head;
while(first && second)
{
first = first->next;
second = second->next;
if(second) second = second->next;
else return NULL;
if(first == second)
{
first = head;
while(first != second)
{
first = first->next;
second = second->next;
}
return first;
}
}
return NULL;
}
};
题目里好像并没有说节点值互不相同啊
题目里说了。节点值互不相同。
set方法为啥输出的是3也能ac啊