Java之单链表问题解决案例讲解

单链表

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

问题

问题1：给定一个单链表，判断链表中是否有环

问题2：给定一个链表，返回链表开始入环的第一个节点，如果无环，则返回null

class Node{
    public int data;
    Node next;
    public Node(int data){
        this.data=data;
        this.next=null;
    }
}
public class linkedList {
    /*给定一个链表，判断链表中是否有环
    思路： 如果链表有环的话，定义两个节点fast,slow。让fast一次走两步，slow一次走一步；
    如果能相交，即fast=slow，说明有交点，且如果有环，节点的next也不会为空
     */
    public Node head;
    public boolean hasCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null&&fast.next!=null){//如果把fast.next写下前面，一旦fast为空，则会空指针异常
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

    //给定一个链表，返回链表开始入环的第一个节点，如果无环，则返回null
    public Node detectCycle(){
        /*定义fast与slow,fast前进2格，slow前进一格，如果有交点的话，fast与slow第一次相遇时，fast的路程为slow的2倍，
        如设从头节点到入环节点的距离为X，令入环节点到fast,slow第一次相遇距离为Y，环的总长度为C的话;可得公式：2（X+Y）=X+Y+NC；
        得X=NC-Y，令N等于1，X=C-Y;此时让slow从头节点开始走，当于速度相同的fast相遇时，则为入环的节点。
        */
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){//第一次相遇
                break;
            }
        }
        if(fast==null&&fast.next==null){
            return null;
        }
        //此时让slow从头节点开始，与fast以相同速度前进，遇到则为入环的第一个节点
        slow=this.head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

到此这篇关于Java之单链表问题解决案例讲解的文章就介绍到这了,更多相关Java之单链表问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java单链表反转图文教程

    Java单链表反转图文教程

    前言 最近在回顾链表反转问题中,突然有一些新的发现和收获,特此整理一下,与大家分享

  • 用JAVA实现单链表，检测字符串是否是回文串

    一.需求 使用JAVA实现单链表,使用单链表检测字符串是否是回文串 二.需求分析 回文串最重要的就是对称,那么最重要的问题就是找到那个中心,用快指针每步走两格,当他到达链表末端的时候,慢指针刚好到达中心,慢指针在遍历过程中(快指针到达末端时)把走过的节点进行反向操作,此时从中位点分为前后两部分,此时前半部分的指针开始往回指(取next的时候,取的是前一个节点),而慢指针继续向前,跟前半部分的数据依次进行比对,当慢指针扫完整个链表,就可以判断这是回文串,否则就提前退出,同时在前半部分往回遍历的过程

  • Java实现单链表反转的多种方法总结

    Java实现单链表反转的多种方法总结

    对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查 一.原地反转 1.新建一个哨兵节点下一结点指向头结点 2.把待反转链表的下一节点插入到哨兵节点的下一节点 反转之前的链表:1–>2–>3–>4>–>5 加入哨兵节点:dummp–>1–>2–>3–>4>–>5 原地反转: 定义:prev=dummp.next; pcur=prev.next; prev.next=pcur.next; pcur.next=dummp.next; d

  • Java如何实现单链表的增删改查

    一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu

  • Java单链表的简单操作实现教程

    前言 用Java实现单链表的简单操作,阅读本文和上一篇文章体会Java中类与C++中结构体指针的区别 提示:以下是本篇文章正文内容,下面案例可供参考 一.基本实现思路 构造结点类 构造链表类 具体测试实现 二.代码实现 1.定义结点类 package list.test01; /* *定义结点类 */ public class Node { private int data; public Node next; public Node(int data) { this.data = data;

  • Java数据结构之单链表详解

    Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • java数据结构基础:单链表与双向链表

    目录 单链表: 实现思路: 代码实现: 双向链表: 实现思路: 代码实现: 总结 单链表: 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个节点的指针 实现思路: 节点类SingleNode中保存数据和指向下一个节点的指针 单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法 对于链表方法,涉及到位置查找,如在指定位置增加.删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置. 对于节点的增加

  • java实现简单单链表

    java实现简单单链表

    本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下 一.定义: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(相当于JAVA中的引用,指示后继元素存储位置,),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 二.结构: 如图所示,data就是当前节点的数据,next是指针,指针存放的是内存地址,是当前结点的下一结点内存地址,顺着这个地址就能找

  • Java之单链表问题解决案例讲解

    单链表 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 问题 问题1:给定一个单链表,判断链表中是否有环 问题2:给定一个链表,返回链表开始入环的第一个节点,如果无环,则返回null class Node{ public int data; Node next; public Node(int da

  • Java对文件进行基本操作案例讲解

    File文件类 java.io.File是文件和目录的重要类(JDK6及以前是唯一) 目录也使用File类进行表示 File类与操作系统无关,但会受到操作系统的权限限制 常用方法 createNewFile , delete , exists , getAbsolutePath , getName , getParent , getPath isDirectory , isFile , length , listFiles , mkdir , mkdirs File不涉及到具体的文件内容.只会涉

  • Java实现单链表翻转实例代码

    Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

  • java 实现单链表逆转详解及实例代码

    java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • java实现单链表之逆序

    下面一段代码准确的介绍了java实现单链表逆序,具体内容就不做详解了,有需要的朋友可以直接拷贝了 package com.ckw.mianshi; /** * java 实现单链表的逆序 * @author Administrator * */ public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static

  • java实现单链表、双向链表

    本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {

  • Java之SpringCloudAlibaba Sentinel组件案例讲解

    Java之SpringCloudAlibaba Sentinel组件案例讲解

    Sentinel 是什么 随着微服务的流行,服务和服务之间的稳定性变得越来越重要.Sentinel 以流量为切入点,从流量控制.熔断降级.系统负载保护等多个维度保护服务的稳定性. 官网:https://github.com/alibaba/Sentinel 中文官网:https://github.com/alibaba/Sentinel/wiki Sentinel与Hystrix的区别 由于Hystrix不再积极的开发,进入维护阶段,现在越来越多的开发者在项目中使用Spring Cloud Al

随机推荐