剑指offer——链表中环的入口节点（c++)

本文主要是介绍剑指offer——链表中环的入口节点（c++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

如果一个链表有环，如何找出环的入口节点？

思路

第一步是如何确定一个链表包含环：可定义两个指针，同时从链表的头节点出发，一个指针每次走一步，另一个指针每次走两步，如果两者相遇，那么链表中就包含环；否则，链表就不包含环。
第二步是如何找环的入口：同样的，同时从链表的头节点出发，定义两个指针，如果链表的环有n个节点，则让一个指针在链表上向前移动n步，然后两个指针同时向前移动，两者相遇时的节点就是环的入口节点。
剩下的问题是如何得到环的数目，接着第一步，从两个指针相遇的节点出发，一边向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。

class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* head){ListNode* meetingNode = MeetingNode(head);if(meetingNode == NULL)return NULL;// 得到环中结点的数目int numsInLoop = 1;ListNode* node1 = meetingNode;while(node1->next != meetingNode){node1 = node1->next;++numsInLoop;}// 先移动pNode1，次数为环中结点的数目node1 = head;for(int i = 0; i < numsInLoop; ++i)node1 = node1->next;// 再移动pNode1和pNode2ListNode* node2 = head;while(node1 != node2){node1 = node1->next;node2 = node2->next;}return node1;}ListNode* MeetingNode(ListNode* head){if(head == NULL)return NULL;ListNode* low = head, *fast = head;while(fast->next && fast->next->next){low = low->next;fast = fast->next->next;if(low == fast)return fast;}return NULL;}
};