《剑指offer》 第23题 链表中环的入口节点

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

  经典的快慢指针的题。一快一慢，快的追上慢的就说明有环，快的没追到慢的，就说明快的会跑到链表尾部，先为Null。通过这个步骤可以判断是否有环。但是要找到环的入口节点就得具体分析了。

解法1：

思路
1.先确定是否有环。
2.确定环中结点的数目n：指针走一圈，边走边计数。
3.找到环的入口：两个指针都从头结点开始，一个先走n步，两个相差为n的指针同时运动，最终会在入口相遇。设单链部分长为x，环长为n，一个走x步，另一个则走了n+x步，所以正好在入口处相遇。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)   {
        ListNode node = meetingNode(pHead);//拿到相遇的节点
        if(node == null)
            return null;
        //得到环中的节点个数
        int count =1 ;
        ListNode p1 = node;
        while(p1.next != node){
            p1 = p1.next;
            count++;
        }
        //p1先走N步
        p1 = pHead;
        for(int i=0; i<count;i++){
            p1 = p1.next;
        }
//      同时移动
        ListNode p2 = pHead;
        while(p1!=p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
     //返回换相遇的节点
    public  ListNode meetingNode(ListNode head) {
        if(head==null)
            return null;        
        ListNode slow = head.next;
        if(slow==null)
            return null;        
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
            if(slow==fast)
                return fast;
            slow=slow.next;
            fast=fast.next.next;            
        }
        return null;
    }
}

解法2：

思路：这个解法需要动脑子找规律，像我这种不会画图的人，感觉语言很难解释清楚。我就推导一下过程哈，其实不难，看不懂下列推导的可以看图解（其他大佬的哈）
  一共设置3个指针，一快两慢。其中让一快一慢去做相遇的动作（快是慢的两倍速度）。当快慢指针相遇时，设快指针走了a步，慢指针走了b步(a=2b)。其次设单链部分长为x，环长为y，快指针在环上绕了n圈还多k步，慢指针绕环走了m圈还多k步。将a、b写成和链表长度有关的方程，有a=x+ny+k，b=x+my+k。消去a和b，得到x = ny - 2my - k。令c = ny-2my = (n-2m)y，也就是说，c是环长y的整数倍。注意，慢指针此时停在离环入口距离为k的地方，而再走y-k步就是回到了环的起始点，那么如果不介意的话，请让这个慢指针多走几圈，走的距离是c-k这么多，还是能回到入口点。而这个距离正好等于x即单链部分长度。
  c-k =(n - 2m - 1)*y +(y - k)可以看到c-k确实能让慢指针回到原点，只不过多走n-2m-1圈
  这就说明当第三个指针从原点开始走到入口时，慢指针同时从K处动身，最终两个慢指针将会在入口处相遇。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if( pHead==null)
            return null;
        ListNode fast= pHead;
        ListNode slow= pHead;
        ListNode slow2= pHead;
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                while(slow2!=slow){
                    slow2=slow2.next;
                    slow=slow.next;
                }
                return slow2;
        }
    }
    return null;
    }
}

解法3：

  想到使用Set集合，将节点不断放入set集合，当某个节点重复出现时，就说明这个节点是环的节点。而第一次出现的重复节点就是环的入口节点

import java.util.HashSet;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null)
            return null;
        HashSet<ListNode> nodes = new HashSet<>();
        while (pHead != null) {
            if(nodes.contains(pHead)){
                return pHead;
            }else{
                nodes.add(pHead);
                pHead = pHead.next;
            }
        }
        return null;
    }
}