首页 > 代码库 > 链表中的环
链表中的环
判断链表是否有环，定义指针一快（走2部）一慢（走1部），相遇即有环。
bool isCircle(listNode* head){ if(NULL == head) return false; listNode* slowNode = head->next; if(NULL == slowNode) return false; listNode* fastNode = head->next; while(fast != NULL && slow != NULL){ if(fast == slow) return true; slowNode = slowNode->next; fastNode = fastNode->next; if(fastNode != NULL) //快指针时刻检查，是否为空 fastNode = fastNode->next; } return false; }
两个指针，一快一慢，有环，则相遇必在环内，找出相遇节点
listNode* meetingNode(listNode* head){ if(NULL == head) return NULL; listNode* slowNode = head->next; if(NULL == slowNode) return NULL; listNode* fastNode = head->next; while(fast != NULL && slow != NULL){ if(fast == slow) return fast; slowNode = slowNode->next; fastNode = fastNode->next; if(fastNode != NULL) //快指针时刻检查，是否为空 fastNode = fastNode->next; } return NULL; }
接下来，就可以统计环中节点个数，找出环的入口节点
设节点个数为n，快指针先走n步，然后快慢指针一起一步一步走，相遇节点即环入口节点。
链表中的环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。