面试题23：链表中环的入口节点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路：这道题需要分步骤完成，首先需要通过快慢两个指针判断是否有环；接着如果有环从两个指针相遇的节点开始一边向前一遍计数，得到环的节点数n，最后通过一个指针先行n步再两个指针同时前进的方法确定环的入口。思维导图如下：

23 链表中环的入口节点.png

代码实现：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        meeting = self.MeetingNode(pHead)
        if meeting == None:
            return None
        pNode1 = pHead
        NodeNumber = 1
        while(pNode1.next != meeting):
            pNode1 = pNode1.next
            NodeNumber +=1
        #先移动n步
        pNode1 = pHead
        for i in range(NodeNumber):
            pNode1 = pNode1.next
        #同时移动两个指针
        pNode2 = pHead
        while(pNode1 != pNode2):
            pNode1 = pNode1.next
            pNode2 = pNode2.next
        return pNode1

    def MeetingNode(self, pHead):
        # write code here
        if pHead is None:
            return None
        fast = pHead
        slow = pHead
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return slow
        return None

提交结果：

牛客网提交结果.png