本文主要是介绍剑指offer23——链表中环的入口节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
判断单链表中有没有环，如果有找到环的入口节点。
三个问题：
1、如何确定链表中包含环：两个指针，一个指针一次走一步，一个指针一次走两步。如果走得快的指针追上了走得慢的指针，则说明链表包含环； 如果走得快的指针走到了链表末尾（p->next == NULL）都没有追上第一个指针，则无环。
2、如何找到环的入口：定义两个指针p1,p2指向头结点，如果环有n个结点， 则p1先移动n步，然后两个指针以相同的速度向前移动。当p2指向环的入口节点时，p1已经围绕着环走了一圈又回到了入口节点。
3、如何得到环中节点数目：1中相遇的两个指针指向的结点一定在环中，可以从这个节点出发，一边继续移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。
//判断链表内是否包含环
//找到快慢指针相遇的节点，此节点必定在环内
ListNode* meetingNode(ListNode* head){if(head == NULL)return NULL;ListNode* slow = head->next;if(slow == NULL)return NULL;ListNode* fast = slow->next;while(fast != NULL && slow != NULL){if(fast == slow)return fast;slow = slow->next;fast = fast->next;if(fast != NULL)fast = fast->next;}return NULL:
}//得出环中节点数目，并找到环的入口节点
ListNode* EntryNodeOfLoop(ListNode* head){ListNode* meetingNode = meetingNode(head);if(meetingNode == NULL)return NULL;//找到环中节点数目int nodesInLoop = 1；ListNode* m = meetingNode;while(m->next != meetingNode){m = m->next;nodesInLoop++;}m = head;for(int i=0; i<nodesInLoop; ++i){m = m->next;}ListNode* n = head;while(m != n){m = m->next;n = n->next;}return m;
}
这篇关于剑指offer23——链表中环的入口节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
