【leetcode82】Linked List Cycle
【leetcode82】Linked List Cycle
fengsehng 发表于1年前
【leetcode82】Linked List Cycle
  • 发表于 1年前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

题目描述:

判断有序list是不是环

要求:

时间复杂度o(n)

原文描述:

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

思路:

  • 设置两个指针,一个快指针,每次走两步,一个慢指针,每次走一步
  • 如果块指针==慢指针,那么包含环
  • 注意判断空值和长度为一的情况
    -

代码:

/** * 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 fast = head;
        ListNode slow = head;

        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }

        return false;
    }
}

更多leetcode题目,请看我的leetcode专栏。链接如下:

leetcode专栏

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

共有 人打赏支持
粉丝 4
博文 284
码字总数 214494
×
fengsehng
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: