首页 > 其他分享 >环形链表

环形链表

时间:2022-10-12 23:33:47浏览次数:46  
标签:head return 环形 fast next 链表 null

环形链表

一,题目描述

给定一个链表的头节点,判断链表中是否存在环。存在返回true,不存在返回false。

二,解题思路

如果链表无环,遍历后最终都会指向null。如果有环,会重复遍历。

三、解题方法

方法1:遍历
创建一个set集合,遍历整个链表。并存入集合中,当链表有环时,由于set集合的特性。就可一判断是否有环。
代码实现

public class Solution {
    public boolean hasCycle(ListNode head) {

        Set<ListNode> set = new HashSet<ListNode>();
        while(head != null){
            if(!set.add(head)){
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

方法2:快慢指针
使用快慢指针,慢指针步长为1,快指针步长为2,如果有环,快慢指针总会相遇。如果无环,最终快指针会首先指向null。
代码实现:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null || head.next == null){
            return false;
        }

        ListNode low = head;
        ListNode fast = head.next;

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

            low = low.next;
            fast = fast.next.next;
        }

        return true;
    }
}

标签:head,return,环形,fast,next,链表,null
From: https://www.cnblogs.com/zjjtt/p/16786519.html

相关文章

  • 链表的逆置
    本题要求实现一个函数,将给定单向链表逆置,即表头置为表尾,表尾置为表头。链表结点定义如下:structListNode{intdata;structListNode*next;};函数接口定义......
  • TZOJ 7871:维护序列 单链表应用(创建/查询/插入/删除)
    描述 给定一个长度为n的整数序列。现在有m个操作,操作分为三类,格式如下:(1)1i:询问序列中第i个元素的值,保证i小于等于当前序列长度。(2)2iv:在序列中第i个元素前加......
  • 单链表-Python实现-jupyter->markdown 格式测试
    单链表引入顺序表理解Python变量的本质:变量存储的不是值,是值的地址理解Python的"="表示的是指向关系案例:交换a,b的值,a=10,b=20a,b=20,10t0:a这块内存(也有id),......
  • 中等-817. 链表组件
    解题思路:对链表循环执行结果:通过执行用时:232ms,在所有 JavaScript 提交中击败了36.36%的用户内存消耗:44.5MB,在所有 JavaScript 提交中击败了93.18%的用户通......
  • 817. 链表组件
    817.链表组件给定链表头结点 head,该链表上的每个结点都有一个唯一的整型值。同时给定列表 nums,该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的......
  • 数据结构 链表(第7、8天)
    链表这里面的链表题比较简单,只要会遍历链表、删除链表节点、反转链表这些基本操作就行。必要时可以画图辅助理解。141.环形链表给定一个链表,判断是否有环。思路:快慢指......
  • //按照完全二叉树的层次顺序一次输入节点信息建立二叉链表的算法
    //按照完全二叉树的层次顺序一次输入节点信息建立二叉链表的算法#include<stdio.h>#include<stdlib.h>typedefcharDataType;typedefstructnode{DataT......
  • 算法每日一题(反转单链表)C语言版
     在本篇文章里,我将分享一道很经典的算法题———反转链表,并且分享多种方法去解决方法,希望可以帮助到你......
  • 「Java 数据结构」:手撕单链表的增删改查及大厂面试题。
    目录​​一、单链表的增删改查​​​​1、创建结点     ​​​​2、单链表的添加操作​​​​3、单链表的删除操作​​​​4、单链表的有效结点的个数​​​​二、......
  • 链表结构
    链表一、链表的分类1.1单项链表每个node节点指向下一个节点。然后有个head节点指向第一个节点,尾节点指向null。也可以有个last节点指向最后一个节点。这样能快速获取......