做网站所需要哪方面的知识,网站更新,提升网站浏览量,后台登录wordpress文章目录 判断链表中是否有环链表中环的入口结点 判断链表中是否有环
题目链接#xff1a;判断链表中是否有环
解题思路1#xff1a;快慢指针
代码如下#xff1a; bool hasCycle(ListNode *head) {if(head nullptr) return false;ListNode* fast head;ListNode* slow … 文章目录 判断链表中是否有环链表中环的入口结点 判断链表中是否有环
题目链接判断链表中是否有环
解题思路1快慢指针
代码如下 bool hasCycle(ListNode *head) {if(head nullptr) return false;ListNode* fast head;ListNode* slow head;while(fast!nullptr fast-next ! nullptr){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;}解题思路2hash法
我们把所有的节点放到哈希表中我们遍历整个链表如果存在重复的相同节点那就证明链表中有环
代码如下 bool hasCycle(ListNode *head) {mapListNode*, int mp;ListNode* cur head;while(cur ! nullptr){if(mp[cur] 1) return true;mp[cur] 1;cur cur-next;}return false;}链表中环的入口结点
题目链接链表中环的入口结点
解题思路1hash法记录第一次重复的节点
代码如下 ListNode* EntryNodeOfLoop(ListNode* pHead) {mapListNode*, int mp;ListNode* cur pHead;while (cur ! nullptr) {if (mp[cur] 1) return cur;mp[cur] 1;cur cur-next;}return nullptr;}解题思路2快慢指针
上面我们用快慢指针来判断一个链表是否有环我们也可以通过快慢指针来找到环的入口节点。我们要找到快慢指针之间步数的数学关系借助数学关系来找到环的入口节点 假设从头结点到环的入口节点一共有a个节点环中的节点一共有b个设快指针走的步数为f慢指针走的步数为s那么有步数之间有这样的数学关系
f 2 * s 快指针一次走两步慢指针一次走一步f s nb 当快慢指针相遇时快指针一定比慢指针多走了nb步意思就是多绕环了n圈
所以可以得出s nbf 2nb
当快慢指针相遇时慢指针已经走了nb步快指针走了2nb步同时我们要走到环的入口节点需要走a kb 步而这时慢指针的nb只要再走a步即可到达入口所以我们把快指针移动到头节点之后再让两个指针一次走一步往前走当他们相遇时所处的节点就是入口节点
代码如下 ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast pHead;ListNode* slow pHead;while(fast ! nullptr){slow slow-next;if(fast-next nullptr) return nullptr;//链表中无环fast fast-next-next;if(fast slow){//快慢指针相遇fast pHead;//让快指针重新指向pHeadwhile(fast ! slow){//通过两个指针的相遇控制fast走a步fast fast-next;slow slow-next;}return fast;//此时fast即是入口节点直接返回}}return nullptr;}
