网站空间/搜索引擎有哪些好用

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

解析：采用双指针法（LeetCode大神思路）：

①fast：每次走两步

②low：每次走一步

假设入口为q点，两指针会在p点相遇，在最简单情况下，即fast转了一圈追上了low，此时fast的距离：a+b+c+b；low走的距离：a+b，因此有关系：a+b+c+b=2(a+b)-------->a=c；那么可以继续让low走下去；同时让fast回到head，改为每次走一步，则有：新fast走过a（=c）；low走过c（=a），两个指针将在q点相遇，找到入口；

代码：

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        //如果空链表或节点的next为空，则肯定没有环
        if(pHead == null || pHead.next == null)
            return null;
        ListNode fast = pHead;
        ListNode low  = pHead;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low  = low.next;
            if(fast == low)
                break;
        }
        fast = pHead;
        while(fast != low){
            fast = fast.next;
            low  = low.next;
        }
        return fast;
    }
}

************************************************************************************************************************************

利用HashSet实现

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null)
            return null;
        HashSet<ListNode> node = new HashSet<>();
        while(pHead != null){
            if(node.contains(pHead)){
                return pHead;
            }else{
                node.add(pHead);
                pHead = pHead.next;
            }
        }
        return null;
    }
}