142. 环形链表 II

题目:https://leetcode-cn.com/problems/linked-list-cycle-ii/

代码:

class Solution {

    public ListNode detectCycle(ListNode head) {
        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //进行赛跑
        do {
            //跑到尽头证明不存在环
            if (fast == null || fast.next == null) {
                return null;
            }
            //慢指针走一步
            slow = slow.next;
            //快指针走两步
            fast = fast.next.next;
        } while (fast != slow);

        //快指针套若干圈后追上慢指针,证明有环
        ListNode first = head;
        //first每走一个节点就让fast跑一圈,如果发现first等于fast,则first是环的起点
        while (true) {
            do {
                if (first == fast) {
                    return first;
                }
                fast = fast.next;
            }while (fast != slow);
            first = first.next;
        }
    }

}

141. 环形链表的基础上进行改造,使用快慢指针找到存在环之后,我们新定义一个first指针,通过判断first指针是否在环中来获取环的起点,如果不在环中则让first = first.next。

那么我们如何判断first是否在环中呢?我们可以让slow指针停止作为标杆,fast指针继续循环转圈,但步长修改为1,通过判断fast是否等于first来确定是否在环中,slow为标杆防止死循环,具体操作见红色部分代码。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏