区块链系统app开发/百度推广seo是什么意思

题目：
如果一个链表中包含环，如何找出环的入口结点？

如此图中所示链表，环的入口结点为结点3。

分析：
1）
要找到环的入口结点，我们首先要确定这个链表中是否包含环？我们可以用两个指针从头开始走，一个指针走得快，一个指针走得慢，如果走的快的指针追上了走的慢的指针，那就证明这个链表存在环。

2）
判断了链表中包含环，我们仍然可以用双指针来找到入口，假如环中一共包含n个结点，那么从环入口开始走一圈再次到达环入口一共需要n步，从头开始到达环入口假如为x步，我们令第一个指针从头开始先走n步，那么这个指针就剩x步到达环入口，这时候让第二个指针从头开始走，第一个指针继续向下走，当二者相遇时的结点就为环的入口结点。这种方法就需要我们知道环中一共包含多少个结点，我们在1）中判断了链表是否包含环，两个指针相遇结点一定在环中，可以从相遇的结点出发，一边移动一边计数，当再次回到这个结点的时候，就可以得到环中结点数目。

综上解决这个问题分为3个步骤：
先判断是否存在环（找到环中相遇的结点）->计算出环中结点数目->找到环的入口结点

ListNode *MeetingNode(ListNode*head){if(head == NULL)return NULL;ListNode *pSlow = head->next;if(pSlow == NULL)   //一个结点 不能成环return NULL;ListNode *pFast = pSlow->next;while(pFast != NULL && pSlow != NULL){ //只判断pFast也可以if(pFast == pSlow)return pFast;pFast = pFast->next;pSlow = pSlow->next;if(pFast != NULL)pFast = pFast->next;}return NULL;}ListNode *detectCycle(ListNode *head){ListNode *meetingNode = MeetingNode(head);if(meetingNode == NULL) return NULL; //不存在环//得到环中结点数目int count = 1;ListNode *p1 = meetingNode;while(p1->next != meetingNode){p1 = p1->next;count++;}p1 = head;for(int i=0;i<count;i++){p1=p1->next;}ListNode *p2 = head;while(p1 != p2){p1 = p1->next;p2 = p2->next;}return p2;}

除此之外，本题也有多处地方考察了代码的鲁棒性，我们在对链表进行移动的时候一定要时刻注意是否访问了NULL，会存在多处令程序崩溃的风险。