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

判断链表中是否有环

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

/**
 * 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;
        
    }
}

思路很简单,定义两个指针,快慢指针,存在速度差。如果单链表,slow一直追不上fast,只能把链表走完,那就是fast为空或者fast.next为空,因为定义了fast的步长为2。如果可以追上,说明存在环。

要注意一开始head为null,或者只有一个节点的情况,一开始直接return,否则程序会越界。

全部评论

相关推荐

群星之怒:1.照片可以换更好一点的,可以适量P图,带一些发型,遮住额头,最好穿的正式一点,可以适当P图。2.内容太少。建议添加的:求职意向(随着投递岗位动态更改);项目经历(内容太少了建议添加一些说明,技术栈:用到了什么技术,还有你是怎么实现的,比如如何确保数据传输稳定的,角色注册用到了什么技术等等。)项目经历是大头,没有实习是硬伤,如果项目经理不突出的话基本很难过简历筛。3.有些内容不必要,比如自我评价,校内实践。如果实践和工作无关千万别写,不如多丰富丰富项目。4.排版建议:建议排版是先基础信息,然后教育背景(要突出和工作相关的课程),然后专业技能(一定要简短,不要长篇大论,写你会什么,会的程度就可以),然后是项目经历(一定要详细,占整个简历一定要超过一半,甚至超过百分之70都可以)。最后如果有一部分空白的话可以填补上校内获得的专业相关的奖项,没有就写点校园经历和自我评价。5.技术一定要够硬,禁得住拷打。还有作息尽量保证正常,不要太焦虑。我24双非本科还是非科班,秋招春招各找了一段实习结果都没有转正,当时都想噶了,最后6月份在校的尾巴也找到一份工作干到现在,找工作有时很看运气的不要急着自我否定。 加油
点赞 评论 收藏
分享
03-21 08:46
已编辑
门头沟学院 C++
只写bug的程序媛:本科能找到好的,真不建议读研,提前占坑比较好,本科找不到好的,也不建议读研,因为两三年之后压力只会更大,唯一的解就是行业好起来
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务