链表中环的入口结点——题解

# -*- 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 pHead.next == None:
            return None
        nodes = set()
        while pHead.next is not None:
            if pHead not in nodes:
                nodes.add(pHead)
                pHead = pHead.next
            else:
                return pHead
        return None

思路：定义两个指针slow和fast，不断移动这两个指针，slow指针移动的步长是1，而fast指针移动的步长是2.
      如果存在环，则slow指针和fast指针一定会相遇，此时输出该节点。
      否则判断fast指针的next是否为空，如果为空的话，说明快指针已经到了链表的尾部，该链表无环。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast !=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                break;
        }
        // 判断跳出循环的原因：如果是break的话就是有环，如果是因为不满足while判别条件那就是没有环
        if (fast ==null || fast.next == null) return null;  // 因为不满足while条件而跳出的
        // 得到环的入口节点
        fast = pHead;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}