河源正规网站建设价格,校园文化网站建设,系统优化加速工具,网站排名seo教程1.环形链表1
看题#xff1a;. - 力扣#xff08;LeetCode#xff09; 思路1#xff1a;哈希表
遍历所有节点#xff0c;每次遍历一个节点时#xff0c;判断该节点是否被访问过。
可以使用哈希表来存储所有已经访问过的节点。每次到达一个节点#xff0c;如果该节点已…1.环形链表1
看题. - 力扣LeetCode 思路1哈希表
遍历所有节点每次遍历一个节点时判断该节点是否被访问过。
可以使用哈希表来存储所有已经访问过的节点。每次到达一个节点如果该节点已经存在于哈希表中则说明该链表是环形链表否则就将该节点加入哈希表中。重复这一过程直到我们遍历完整个链表。 思路2快慢指针
创建两个指针一个快指针一个慢指针快指针一次走两步慢指针一次走一步如果是环形链表则两个指针会相遇所以每走一次判断两个指针是否相等。如果不是环形链表则快指针会走到NULL。 1.1.快慢指针
看图 代码实现
bool hasCycle(struct ListNode *head) {struct ListNode *fasthead;struct ListNode *slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;
}
2.环形链表2
看题. - 力扣LeetCode 目录
1.环形链表1
1.1.快慢指针
2.环形链表2 思路1快慢指针
先上结论下面是一个环形链表node结点位是快慢指针相遇的位置结点phead是入环结点。
其中L的长度等于M的长度知道这个结论后代码就信手拈来了。 下面是证明LM
如果是环形链表那么两个指针会相遇找到相遇的节点node 那么如图设置head到入环的结点的长度为L入环到相遇的结点node的长度为N环的长度为C 那么开始遍历链表当然慢指针slow入环时快指针已经在环里走了至少一圈假设为x圈
当快慢指针相遇时慢指针在环里面走的长度就是N因为快指针的相对于慢指针的速度为1所以每走一步快指针就与慢指针的距离-1直到相遇。 此时
快指针走的路程LNx*C
慢指针走的路程LN
因为快指针的速度是慢指针的两倍所以路程也是慢指针的两倍。
所以
LNx*C2*LN
整理一下
Lx*C-N
处理
Lx-1*CC-N
式中当x取最小值时LC-N 而黑色部分长度就是C-N
此时让head遍历链表node也开始往下走当x取的值不是1时node结点会一直在环里遍历最终head和node一定会在入环结点相遇。
2.1代码
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slowhead;struct ListNode *fasthead;struct ListNode *nodehead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastfast)break;}if(fastNULL||fast-nextNULL)return NULL;while(fast!node){fastfast-next;nodenode-next;}return fast;
}
