141. 环形链表

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

代码:

class Solution {

    public boolean hasCycle(ListNode head) {
        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //进行赛跑
        do {
            //跑到尽头证明不存在环
            if (fast == null || fast.next == null) {
                return false;
            }
            //慢指针走一步
            slow = slow.next;
            //快指针走两步
            fast = fast.next.next;
        } while (fast != slow);
        //快指针套若干圈后追上慢指针,证明有环
        return true;
    }

}

题目有一大堆废话讲解了pos变量的作用,实际上这个变量只是oj系统他自己在用,我们并不需要了解。题目最终要求就是:给定一个链表,判断链表是否存在环,如果可以的话使用O(1)内存解决此问题。

本题有很多取巧的办法来解答,比如:

1、直接改节点的val值为一个特殊值,判断这个特殊值在遍历中是否再次出现。

2、因为题目有给定测试用例最大节点数,所以直接遍历,每遍历一次次数+1,次数大于最大节点数则可以认为存在环。

上述都是投机的办法,实际业务中如果有需求肯定是不能这么干的,那么我们该怎么办呢?我们可以使用快慢指针的办法(龟兔赛跑)。

定义快(兔子),慢(乌龟)两个指针,快指针每次移动2格,慢指针每次移动1格,则快指针一定跑的比慢指针快。

假如快指针一直跑最终出现了null值的情况,则证明跑到了终点,则链表不存在环(为什么只需要判断快指针?因为慢指针跑的慢,跑的都是快指针跑过的路,不需要多次一举)

假如链表中存在环,则快慢指针一定会在环中一直转圈无止尽的跑下去,这个时候,由于快指针跑2格,慢指针跑1格,从物理学角度来说,以慢指针为参照物,则快指针相对于慢指针只跑1格,最终快指针一定会套圈慢指针与慢指针相遇。

综上所述使用代码实现即可。

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

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