温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java的单链表环操作有哪些

发布时间:2021-12-27 16:54:18 阅读:188 作者:iii 栏目:大数据
Java开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

本篇内容介绍了“java单链表环的操作有哪些”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

判断链表中是否有环

先来看一张图:

java的单链表环操作有哪些  

我们能够清楚的看到,在这个单链表中,是有环的。那么使用代码,该如何判断它是否有环呢?

先别着急看代码,先和阿粉一起来分析一下,有了思路,代码实现相对就比较容易。

判断链表中是否有环,可以从头结点开始,依次遍历单链表中的每一个节点。每遍历一个节点,就和前面的所有节点作比较,如果发现新节点和之前的某个节点相同,则说明此节点被遍历过两次,说明链表有环,反之就是没有。

但是仔细看一下这种方法,你会发现这种方法很耗时耗力,因为每遍历一个节点,都要把它和前面所有的节点都比较一遍。别着急,阿粉还有一个很巧妙的方法,就是使用两个指针。这样思路就可以这样想:

使用两个指针,一个快指针,一个慢指针。快指针每次走 2 步,慢指针每次走 1 步。如果链表中没有环,则快指针会先指向 null 如果链表中有环,则快慢指针一定会相遇。

思路打通,咱们就可以使用代码来进行实现了:

/** * 判断链表是否有环 */public class IsHasLoop {    public static class Node{        private int data;        private Node next;        public Node(int data,Node next){            this.data=data;            this.next=next;        }        public int getData(){            return data;        }    }    public static void main(String[] args){        // 初始化单链表        Node node5=new Node(5,null);        Node node4=new Node(4,node5);        Node node3=new Node(3,node4);        Node node2=new Node(2,node3);        Node node1=new Node(1,node2);        // 让 node5 的指针指向 node1 形成一个环        node5.next=node1;        boolean flag=isHasLoop(node1);        System.out.println(flag);    }    public static boolean isHasLoop(Node list){        if (list == null){            return false;        }        Node slow=list;        Node fast=list;        while (fast.next != null && fast.next.next != null){            // 慢指针走一步,快指针走两步            slow=slow.next;            fast=fast.next.next;            // 如果快慢指针相遇,则说明链表中有环            if (slow==fast){                return true;            }        }// 反之链表中没有环        return false;    }}
   

求环长

现在判断链表中是否有环这个问题已经解决了,阿粉觉得不能到此为止,思路就向外扩散了一下,既然有环了,如果想要求环长该怎么办呢?

既然快慢指针相遇了,阿粉记录下此时的位置,接下来再让满指针继续向前走,每次走 1 步,这样当慢指针再次走到相遇时的位置时,慢指针走过的长度不就是环长嘛

public static int getLength(Node list){        // 定义环长初始值为 0        int loopLength=0;        Node slow=list;        Node fast=list;        while (fast != null && fast.next != null) {            // 慢指针走一步,快指针走两步            slow=slow.next;            fast=fast.next.next;            // 第一次相遇时跳出循环            if (slow == fast) break;        }        // 如果 fast next 指针首先指向 null 指针,说明该链表没有环,则环长为 0        if(fast.next == null || fast.next.next == null){            return 0;        }        // 如果有环,使用临时变量保存当前的链表        Node temp = slow;        // 让慢指针一直走,直到走到原来位置        do{            slow = slow.next;            loopLength++;        } while(slow != temp);        return loopLength;}
   

求入环点

既然有环了,也求出了环长,那么入环点应该也知道了吧?阿粉对于求入环点这个问题有点儿懵,就画了一张图出来:

java的单链表环操作有哪些  

如上图,我们假设:

入环点距离头结点距离为 D 入环点与首次相遇点较短的距离为 S1 入环点与首次相遇点较长的距离为 S2 当两个指针首次相遇时,慢指针一次只走 1 步,则它所走的距离为:D+S1 快指针每次走 2 步,多走了 n(n>=1) 圈,则它所走的距离为:D+S1+n(S1+S2) 快指针速度为慢指针的 2 倍,则:2(D+S1)=D+S1+n(S1+S2) 上面等式,整理可得:D=(n-1)(S1+S2)+S2

如果让 (n-1)(S1+S2) 为 0 ,是不是 D 和 S2 就相等了?也就是说,当两个指针第一次相遇时,只要把其中一个指针放回到头结点位置,另外一个指针保持在首次相遇点,接下来两个指针每次都向前走 1 步,接下来这两个指针相遇时,就是要求的入环点。

有点儿像做数学题的感觉,还好阿粉的数学功底还是有那么一丢丢的。

基于上面的思路,代码就很容易实现了:

public static Node entryNodeOfLoop(Node list){        Node slow=list;        Node fast=list;        while(fast.next != null && fast.next.next != null){            // 慢指针走一步,快指针走两步            slow=slow.next;            fast=fast.next.next;            // 第一次相遇时跳出循环            if (slow == fast) break;        }        // 如果 fast next 指针首先指向 null 指针,说明该链表没有环,则入环点为 null        if (fast.next == null || fast.next.next == null){            return  null;        }        // 第一次相遇之后,让一个指针指向头结点,另外一个指针在相遇位置        // 两个指针每次走 1 步,相遇为止,此时相遇节点即为入环点        Node head=list; // 头结点        Node entryNode=slow;    // 相遇节点        while (entryNode != head){            entryNode=entryNode.next;            head=head.next;        }        return entryNode;}

“java单链表环的操作有哪些”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/4047016/blog/4420074

AI

开发者交流群×