题目描述
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null
。
如图:其中权值为3的结点即是环入口
思路:
观察这张图片,发现除了环入口每个结点的前驱只有一个,而环入口的前驱有两个;
因此会想到设一个判断数组来记录每个节点的前驱数,只要有某个数不同于其他的,则该记录对应的结点则为环入口。
找到之后则直接退出记得还要判断如果没有环的话,则遍历结点最后一定为空。因此最后判断一下就好了。🙋
代码
/**
* 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) {
ListNode *a = head;
bool st[1001] = {0};//因为除了环入口每个节点只会被访问一次,所以若遍历过程中发现st的值为1则直接退出
while (a)
{
//若没被访问则将其st数组的值置1,若访问了则此时就找到环的入口,此时a就是指向环入口结点的指针
if (!st[a -> val])
st[a -> val] = 1;
else
return a;
a = a -> next;
}
if (a == NULL)//判断有无环
return NULL;
}
};
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
节点值全部相同怎么办
这里是编号,不是节点值。