链表中环的入口节点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

解法一：

要想知道环的入口节点，则必须至少经过该节点两次，类似于“字符流中第一个只出现一次的字符”，可以记录之前的节点，每输入一个新节点则判断其出现的次数。

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

解法二：

虽然解法一的时间复杂度为O（n），但是空间复杂度为O（n），考虑是否有办法减少空间复杂度。
这个问题可以分成几部分：
1、判断是否存在环。
可以设置两个指针，慢指针每次只一个节点，快节点每次移动两个节点，则经过若干次循环后，若存在环则快慢节点必有相遇的时刻，否则快指针会首先到达链表尾。
2、判断环中节点数。
当快慢指针相遇时，另快节点保持静止，慢节点继续遍历，当快慢节点再次相遇时，便可知道环中节点数count。
3、利用环中节点数找到换的入口节点。
只需要设置两个慢指针m、n，另n先移动count节点，然后m、n节点同时向前移动，当m和n相遇时，便是在环的入口节点。
时间复杂为O（n），空间复杂度O（1）

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return null;
        ListNode l1 = pHead;
        ListNode l2 = pHead;
        int count = 0;
        do{
            if(l2 == null) {
                return null;
            }
            else {
                l1 = l1.next;
                l2 = l2.next.next;
            }
        }while(l1 != l2);
        do{
            count++;
            l1 = l1.next;
        }while(l1 != l2);
        l1 = pHead;
        l2 =  pHead;
        for(int i = 0; i < count; i++) {
            l2 = l2.next;
        }
        while(l1 != l2) {
            l1 = l1.next;
            l2 = l2.next;
        }
        return l1;
    }
}

解法三：

image

与解法二相同，我们可以设两个快慢指针m、n，通过两个指针是否相遇来判断是否含有闭环。
但是当m和n相遇时，我们假设相遇点为B，环为顺时针，环总厂为c，环入口点到相遇点的长度为a，起点到环入口点的距离为x，m速度为n的两倍。则相遇时通过的总距离也为两倍：
Sm=2Sn
Sm=x+nc+a
Sn=x+mc+a
所以可以得到x=（n-2m-1）c+c-a
c-a为橙色部分。
所以我们可以令一个指针这时从起点出发，慢指针n继续前进，当两指针相遇时便为环的入口点。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode l1 = pHead;
        ListNode l2 = pHead;
        int count = 0;
        //检查l1和l2是否会相遇
        do{
            if(l2 == null) {
                return null;
            }
            else {
                l1 = l1.next;
                l2 = l2.next.next;
            }
        }while(l1 != l2);
        //设置从头出发的指针
        l2 =  pHead;
        while(l1 != l2) {
            l1 = l1.next;
            l2 = l2.next;
        }
        return l1;
    }
}

解法四：

断链法：
由于题目已经确定了链表中含有环，如果允许对输入进行修改的话，可以将链表逐步断链，最后剩下的节点便为环的入口节点。

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