25 环形链表

给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环则返回true。 否则返回false。示例 1输入head [3,2,0,-4], pos 1输出true解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出true解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出false解释链表中没有环。提示链表中节点的数目范围是[0, 104]-105 Node.val 105pos为-1或者链表中的一个有效索引。进阶你能用O(1)即常量内存解决此问题吗思路1哈希表1、将链表的节点放入哈希表中每经过一个节点都查询hash表是否已经存在相同的节点若存在则返回true证明链表呈环状。若不存在则把节点加入哈希表中继续往下一个节点走。class Solution { public: bool hasCycle(ListNode *head) { if(!head||!head-next) return false; ListNode *pMovehead; unordered_setListNode* _set; while(pMove){ auto it_set.find(pMove); if(it!_set.end()) return true; _set.insert(pMove); pMovepMove-next; } return false; } };思路2快慢指针1、两个指针一个每一次走一格一个每一次走两格。2、假如链表不呈环状慢指针永远都追不上快指针直到走到链表的尾节点。3、假如链表呈环状快指针总会有快过慢指针整整一圈的时候这时候两个指针正好相等。class Solution { public: bool hasCycle(ListNode *head) { if(!head||!head-next) return false; ListNode *sMovehead; ListNode *fMovehead-next; while(sMovefMove){ if(sMovefMove) return true; if(sMove) sMovesMove-next; if(fMove) fMovefMove-next; if(fMove) fMovefMove-next; } return false; } };推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接