【剑指offer-55】链表中环的入口结点

• 考点：链表
• 时间限制：1秒
• 空间限制：32768K
• 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

---

思路：

两个结论：
1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。
证明结论2：
设：
链表头到环入口长度为–a
环入口到相遇点长度为–b
相遇点到环入口长度为–c

则：相遇时
快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。
慢指针路程=a+b
快指针走的路程是慢指针的两倍，所以：
（a+b）*2=a+(b+c)k+b
化简可得：
a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

代码：

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        while (fast != null && fast.next != null) {
            // 快指针走两步, 慢指针走一步
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        
        // 现在fast在相遇点了
        if (fast == null || fast.next == null) {
            return null;
        }
        
        // slow从头结点触发
        slow = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
        
    }
}

我的问题：

1. 要检查fast和fast.next不等于null，否则可能只有一个节点或者没有节点的情况，这种情况要直接返回null。

---

其他思路1：

利用了HashSet，插入对象，add方法，如果插入成功，元素不存在set中，返回true。如果存在返回false。
所以最终如果重新回到环当中了，那么就是环的入口，返回当前节点即可。

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

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

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

---

其他思路2：

如果链表中环 有n个结点，指针P1在链表上向前移动n步，然后两个指针以相同的速度向前移动。
当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
所以首先要得到环中结点的数目。

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    // 一快一慢的指针相遇处的节点，这个节点一定在环中
    public static ListNode meetingNode(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode slow = head.next;
        ListNode fast = slow.next; // 快的节点走在慢的节点的前一个
        
        while (slow != null && fast != null) {
            if (slow == fast) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
            
            if (slow != fast) {
                fast = fast.next; // fast走两步，slow走一步
            }
        }
        return slow;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode meetingNode = meetingNode(pHead);
        if (meetingNode == null) {
            return null;
        }
        
        // 得到环中节点的个数
        int count = 1;
        ListNode p = meetingNode;
        while (p.next != meetingNode) {
            p = p.next;
            count++;
        }
        
        // 移动p
        p = pHead;
        for (int i = 0; i < count; i++) {
            p = p.next;
        }
        
        // 移动p和q 这个时候p比q先走了n个节点，也就是环的个数，然后他们同时前进
        //  当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
        ListNode q = pHead;
        while (p != q) {
            p = p.next;
            q = q.next;
        }
        return p;
    }
}

---