环形链表找入口节点（Python and C++解法），,题目：给定一个链表，

题目：

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。

说明：不允许修改给定的链表。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii

思路：

分三个环节完成：

　　第一环节判断是否有环，使用快慢指针进行操作；

　　第二环节计算环中节点的数量，如果有环，相遇点一定在环内，计算再次走到相遇点经过的结点数即可；

　　第三环节找入口节点，在已知环的节点数量countCycle的前提下，使一个指针从头先走countCycle步，然后使另一个指针从头同步开始走，它们的相遇点就是环的入口点，因为nodeA先走countCycle步后离入口点的距离与此时B离入口点的距离相同。

Python解法：

 1 class ListNode: 2     def __init__(self, x): 3         self.val = x 4         self.next = None 5  6 class Solution: 7     def detectCycle(self, head: ListNode) -> ListNode: 8         slow = head 9         fast = head10         while fast and fast.next:11             slow = slow.next12             fast = fast.next.next13             if fast == slow:14                 meetNode = fast  # 相遇点15                 break  # 找到相遇点后跳出循环16         if fast == None or fast.next == None:17             return None  # 链表没有环18 19         slow = meetNode.next20         countCycle = 1  # 计算环的节点数量21         while slow != meetNode:22             countCycle += 123             slow = slow.next24 25         nodeA = head26         nodeB = head27         while countCycle:28             nodeA = nodeA.next29             countCycle -= 130         while nodeA != nodeB:  # 再次相遇节点就是入口节点31             nodeA = nodeA.next32             nodeB = nodeB.next33         return nodeA

C++解法：

 1 struct ListNode { 2      int val; 3      ListNode *next; 4      ListNode(int x) : val(x), next(NULL) {} 5  }; 6  7 class Solution { 8 public: 9     ListNode *detectCycle(ListNode *head) {10         // 判断是否有环11         ListNode *slow = head;12         ListNode *fast = head;13         ListNode *meetNode;14         while (fast && fast -> next) {15             slow = slow -> next;16             fast = fast -> next -> next;17             if (fast == slow) {18                 meetNode = fast;19                 break;                20             }21         }22         if (fast == NULL || fast -> next == NULL)23                 return NULL;24         // 计算环中节点的数量25         int countCycle = 1;26         slow = meetNode -> next;27         while (slow != meetNode) {28             slow = slow -> next;29             countCycle += 1;30         }31 32         // 找入口节点33         ListNode *nodeA = head;34         ListNode *nodeB = head;35         while (countCycle--)36             nodeA = nodeA -> next;37         while (nodeA != nodeB) {38             nodeA = nodeA -> next;39             nodeB = nodeB -> next;40         }41         return nodeA;42     }43 };

环形链表找入口节点（Python and C++解法）