55. 链表中环的入口结点

55. 链表中环的入口结点

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

思路
链表有环的意思就是，最后一个节点的next指向了前面的某个节点，链表没有None的链表尾部出口。
思路一：
引入辅助空间，用一个列表保存已经遍历过的节点，如果再次出现，则说明这个节点就是链表环的入口节点。
思路二：
设：链表长度为N，链表环长度为m
1.用两个指针来遍历这个链表，一个每次走一步，一个每次走两步，两个指针会在链表环中的节点相遇。
2.然后继续遍历其中的一个，步长为1，可以计算出链表环中节点的个数m。
3.重新遍历链表，一个指针从头结点0开始(距链表环入口节点N-m)，另一个节点从节点m开始(距链表环入口节点也是N-m)，两个节点会在链表环入口节点处相遇，于是得到链表环入口节点。

代码实现
思路一：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        hashList= []
        headNode = pHead
        while headNode:
            if(headNode == None):
                return None
            if(headNode in hashList):
                return headNode
            else:
                hashList.append(headNode)
            headNode = headNode.next

思路二：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead or not pHead.next or not pHead.next.next:
            return None
        # 用两个指针来遍历这个链表，一个每次走一步，一个每次走两步，两个指针会在链表环中的节点相遇。
        headSlow = pHead
        headFast = pHead.next
        while (headSlow != headFast):
            if headSlow.next == None or headFast.next.next == None:
                return None 
            headSlow = headSlow.next
            headFast = headFast.next.next
        # 此时headSlow = headFast 在环中某节点相遇
        # 继续遍历其中的一个，步长为1，遍历headFast
        count = 1
        headFast = headFast.next
        while(headSlow != headFast):
            headFast = headFast.next
            count += 1
        # count为链表环中节点的个数

        # 重新遍历链表，一个指针从头结点0开始(距链表环节点N-m)，另一个节点从节点m开始(距链表环入口节点是N-m)
        # 两个节点会在链表环入口节点处相遇，于是得到链表环入口节点。
        headSlow = pHead
        headFast = pHead
        for i in range(count):
            headFast = headFast.next
        while(headSlow != headFast):
            headSlow = headSlow.next
            headFast = headFast.next
        return headSlow