题解 | #判断链表中是否有环#

判断链表中是否有环

https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

使用快慢指针的方法判断链表是否有环。快指针每次向前移动两个节点,慢指针每次向前移动一个节点,如果链表有环,则快指针一定会追上慢指针,如果链表没有环,则快指针会提前到达链表尾部。

具体步骤如下:

  1. 初始化快指针fast和慢指针slow,都指向链表的头节点head。
  2. 当快指针fast和快指针fast.next不为空时,执行以下操作:快指针fast每次向前移动两个节点,慢指针slow每次向前移动一个节点。如果快指针fast和慢指针slow相等,说明链表有环,返回true。
  3. 如果快指针fast或快指针fast.next为空,说明链表没有环,返回false。

时间复杂度分析:

快指针每次移动两个节点,慢指针每次移动一个节点,因此快指针最多移动n/2次。其中n为链表的长度。所以时间复杂度为O(n)。

空间复杂度分析:

只使用了两个指针,即快指针和慢指针,所以空间复杂度为O(1)。

全部评论

相关推荐

牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 13:05
TMD找工作本来就烦,这东西什么素质啊😡
Beeee0927:hr是超雄了,不过也是有道理的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务