剑指offer 之 链表中环的入口节点

题目

寻找链表中环的入口节点，如果有环返回入口节点，如果无环返回None。

思路

这道题分两步走：

1. 判断链表是否有环： 两个指针，一快一慢，如果相遇了就说明有环，如果走到头了，就说明没环。很像小学的追及问题哈。
2. 寻找环的入口节点： 这里有一种比较容易想到的方法就是我们再定义一个新的指针，从相遇的节点出发等到它回来，就可以知道环的长度m，然后再用两个指针从头节点出发，一个先走m步，然后两个指针再一起走，相遇的地方就是入口节点。
   不过除了这种方法还有一种更简单的方法：定义两个节点，一个从第一步相遇的节点出发，另一个从头出发，它俩相遇的位置就是环的入口节点。推导见下图：
   

代码

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution:
    '''
    判断一个链表是否有环，如果有，返回环的入口节点；如果没有，返回None
    '''

    def getMeetNode(self, pHead):
        if not pHead:
            return None
        pQuick = pSlow = pHead
        while pQuick and pQuick.next:
            pQuick = pQuick.next.next
            pSlow = pSlow.next
            if pQuick == pSlow:
                return pQuick
        return None

    def entryOfLoop(self, pHead):
        '''
        两步走：
        1. 两个指针一块一满，判断是否有环，相遇则有环，到头则无环
        2. 两个指针，一个从相遇的节点出发，另一个从头出发，它们相遇时的节点就是环的入口节点
        '''
        pMeet = self.getMeetNode(pHead)
        if not pMeet:
            return None
        pNew = pHead
        while pNew != pMeet:
            pNew = pNew.next
            pMeet = pMeet.next
        return pNew

if __name__ == '__main__':
    solution = Solution()
    data = [1, 2, 3, 4, 5, 6]

    #============= case1 有环链表 ==============#
    pHead1 = ListNode(0)
    pCur = pHead1
    for num in data:
        pCur.next = ListNode(num)
        pCur = pCur.next
        if num == 3:
            pMeet = pCur
    pCur.next = pMeet

    #============= case2 无环链表 ==============#
    pHead2 = ListNode(0)
    pCur = pHead2
    for num in data:
        pCur.next = ListNode(num)
        pCur = pCur.next
    
    pEntry1 = solution.entryOfLoop(pHead1)
    pEntry2 = solution.entryOfLoop(pHead2)
    assert(pEntry1.val == 3)
    assert(pEntry2 is None)
    print("Congratulations!")