请注意,本文编写于  271  天前,最后编辑于  271  天前,内容可能已经不具有时效性,请谨慎参考。

NC03

描述

给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。

数据范围: img

要求:空间复杂度 img,时间复杂度 img

示例1

输入:

{1,2},{3,4,5}

返回值:

3

说明:

返回环形链表入口节点,我们后台会打印该环形链表入口节点,即3      

思路

使用NC03快慢指针

当链表无环时返回null

若链表有环 ,两指针在环内第一次相遇时,此时将slow指针指向头结点,然后fast和slow都走一步,直到再次相遇 此时的节点节点就是入环节点。

推导

image-20211003205649378

如上图,是一个环形链表,设环外长度为a,指针slow进入环内后又走了长度b在q点和fast指针相遇

在相遇之前fast指针可能已经在环内走了n圈 故此时fast走过的距离为 a+n(b + c) + b

slow指针走过的距离为 a + b

又因为fast指针走过的距离为slow的二倍 故有 2(a + b ) = a + n(b + c) + b

化简上式得 a = (n - 1)(b + c ) + c

因为b + c 等于环长

所以上式的含义为链表头到入环节点p的距离等于从相遇点到入环节点的距离c 加上n-1被的环长

所以用c, h两个指针从p点和head开始走,当h走完A时,c走过的路为C + (n-1)(C+B),即n圈+C,所以h和c的相遇点为q

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null && pHead.next == null) {
            return null;
        }
        // 判断是否有环

        ListNode slow = pHead;
        ListNode fast = pHead;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 相遇
            if (slow == fast) {
                slow = pHead;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;

    }
}

Q.E.D.


勇敢牛牛,不怕困难!!!