链表--141.环形链表/easy C级理解

2024-01-08 08:54:27

1、题目

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递?。仅仅是为了标识链表的实际情况。

如果链表中存在环?,则返回 true 。 否则,返回 false

?

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例?2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

?

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos-1 或者链表中的一个 有效索引

?

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

Related Topics
  • 哈希表
  • 链表
  • 双指针

2、题目分析

关于快慢指针为什么能检测出环,可以这么思考。 假设存在一个环: 慢指针进入环后,快指针开始追赶慢指针,此时快指针距离慢指针为r,每一次移动,r都会缩小1,在经过r次移动后,二者就会相遇

如果存在环,如何判断环的长度呢?方法是,快慢指针相遇后继续移动,直到第二次相遇。两次相遇间的移动次数即为环的长度。
原因是快慢指针相遇后,也意味在新循环里,快指针距离慢指针的长度=环形链表长度l,此时快慢指针每移动一次,l缩小1,当l缩小为0时,快慢指针相遇。而期间移动的次数就是l的长度。

3、解题步骤

1、定义快慢指针为头结点
2、遍历链表,直到遍历到了链表尾。fast指针至少跟slow一起到链表尾,故是否有链表尾,只要判断fast指针即可
3、在快慢指针移动后再比较,排除初始都指向头结点的情况。如果有环,则链表没有尾,所以在这个判断里结束

4、复杂度最优解代码示例

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            // 遍历链表,直到遍历到了链表尾。fast指针至少跟slow一起到链表尾,故是否有链表尾,只要判断fast指针即可
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 在指针移动后再比较,排除初始都指向头结点的情况。如果有环,则链表没有尾,所以在这个判断里结束
                return true;
            }
        }
        return false;
    }

5、抽象与扩展

环形链表的使用场景:
环形缓冲区:在数据处理中,环形缓冲区是一个重要的概念。环形缓冲区使用环形链表来实现,当缓冲区满时,新的数据会覆盖旧的数据。

文章来源:https://blog.csdn.net/fujuacm/article/details/135356319
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。