剑指Offer(牛客网) 链表中环的入口结点

时间：2023-01-21 08:00:08


题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
来源：
​​​ https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3​​剑指Offer(牛客网) 链表中环的入口结点
我们设链表的无环的部分长度为L1，即有L1个节点，注意，这个L1是包括环的入口节点的。然后让环的长度是L2，这个L2也是包括环的入口节点。这个时候，p1和p2的交点如图所示，交点距离环的入口节点为a（从入口节点沿着行走方向走到交点），即在环的入口节点后面的第a个节点，就是交点，我用红色标记出a。

然后我们来考察一下L1，L2，a，以及n（n是走过的步数，不是走过的节点数，p1一步一个节点，p2一步两个节点）的关系。

忘记说一点了，我们可以明确的是，p1在进入环后，走了不到一圈就在交点处和p2重合，為什麼肯定没有走完一圈？因为p1在进入环的时候，p2和p1之间的距离（沿着行走方向）至多为 L2-1，不可能超过L2-1，因为环的大小也才只有L2 。p2追赶p1，最多只需要走L2-1步，因为每走一步，p1和p2的相对距离减小1，那么p1最多只走了L2-1步，就是最多只经过了L2-1个节点，不可能走完一圈。

现在可以列公式了：

L1+a=n #1 //n是p1走过的节点数

L1+kL2+a=2n #2 //2*n这个是p2走过的节点数，其中的k表示p2可能在环里面走了k圈，k>=1

由#2式减去#1式，有：

k*L2 = n #3

同时由#1和#3得到：

L1+a = k*L2 #4

接着由#4就得到了如下式：

L1 = k*L2 - a = (k-1)*L2 + (L-a)

得到这条式子就拨得云开见月明啊有木有，因为(L-a)表示的是交点与环入口的距离（从交点沿着行走方向到环入口），然后(k-1)是>=0的，因为p2在环中至少绕了一圈，这样我们就发现：L1的长度 = 环长度的整数倍 + 交点与环入口的距离

也就是说，p1再走L1步就可以达到环的入口。问题是L1不是已知的，没关系，在表头设置一个p3指针，p3每步前进一个节点。让p1和p3同时走，每次走1步，等p3和p1重合了，就是到了环口的位置了。Problem solved~

/*
 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||pHead.next==null)return null;
        ListNode fast = pHead;
        ListNode slow = pHead;

        while(fast!=null||slow!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow)break;//用快慢指针法证明有环则跳出
        }
            fast = pHead;//另用一个结点从起点跑起，在此与slow相遇的结点就是入口
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}


标签：

相关文章