排行榜 统计
  • 文章总数:649 篇
  • 评论总数:10704 条
  • 分类总数:4 个
  • 最后更新:4月4日

链表中环的入口结点-【java版数据结构】找到环形链表的入口

本文阅读 2 分钟
首页 网络技巧 正文
本文最后更新于2023年01月24日,已超过831天没有更新。如果文章内容或图片资源失效,请留言反馈,我会及时处理,谢谢!

您阅读这篇文章共耗时:

  原理:我们先判断当前链表是否是环形链表,定位到快慢指针相遇的结点,这是创建一个temp指针指向第一个元素,用temp指针和慢指针继续遍历链表链表中环的入口结点,temp指针和慢指针相遇的结点就是环形链表的入口

  数学分析:

  为什么在快慢指针相遇之后链表中环的入口结点,用temp指针和慢指针去遍历链表时,相遇的结点就是环形链表的入口呢?

  在这里插入图片描述

   //找出循环链表的入口

        public static Node getEntrance(Node first){
            //判断链表是否有环
            //定义两个快慢指针
            Node fast=first;
            Node slow=first;
            Node temp=null;
            //遍历链表,判断两指针是否相遇
            while(slow!=null&&slow.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                //相遇,让新指针指向第一个结点,找到slow指针和temp指针相遇的结点,就是环的入口
                if(fast.equals(slow)){
                    temp=first;
                    continue;
                }
                //是循环链表
                if(temp!=null){
                    temp=temp.next;
                    //相遇了,找到了环的入口
                    if(slow.equals(temp)){
                        break;
                    }
                }
            }
            //返回循环链表的入口
            return temp;
        }

  测试代码:

   package com.company.test;

    /**
     * @ProjectName [数据结构][5]实操
     * @ClassName FastSlowTest
     * @Description // 快慢指针,解决中间值问题
     * @Email 2992794262@qq.com
     * @Author ASUS
     * @Date 2022/1/7
     **/
    public class CycleLinkEntranceTest {
        public static void main(String[] args) {
            Node first=new Node("aa",null);
            Node second=new Node("bb",null);
            Node third=new Node("cc",null);
            Node fourth=new Node("dd",null);
            Node fifth=new Node("ee",null);
            Node sixth=new Node("ff",null);
            Node seventh=new Node("gg",null);
            first.next=second;
            second.next=third;
            third.next=fourth;
            fourth.next=fifth;
            fifth.next=sixth;
            sixth.next=seventh;
            //环形链表
            seventh.next=third;
            Node entrance = getEntrance(first);
            System.out.println("环的入口是:"+entrance.item);
        }
        //找出循环链表的入口
        public static Node getEntrance(Node first){
            //判断链表是否有环
            //定义两个快慢指针
            Node fast=first;
            Node slow=first;
            Node temp=null;
            //遍历链表,判断两指针是否相遇
            while(slow!=null&&slow.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                //相遇,让新指针指向第一个结点,找到slow指针和temp指针相遇的结点,就是环的入口
                if(fast.equals(slow)){
                    temp=first;
                    continue;
                }
                //是循环链表
                if(temp!=null){
                    temp=temp.next;
                    //相遇了,找到了环的入口
                    if(slow.equals(temp)){
                        break;
                    }
                }
            }
            //返回循环链表的入口
            return temp;
        }
        private static class Node{
            T item;
            Node next;
            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }
    }

本文来自投稿,不代表本站立场,如若转载,请注明出处:http://xuan.ddwoo.top/index.php/archives/916/
-- 展开阅读全文 --
SEO外链建设_友情链接越多越好吗?
« 上一篇 08-24
C语言之复杂链表的复制方法(图示详解)
下一篇 » 09-05
------本页内容已结束,喜欢请分享------

感谢您的来访,获取更多精彩文章请收藏本站。

发表评论

本站已加入互联网信息服务许可,请规范您的言行哦~

成为第一个评论的人

作者信息

热门文章

珍惜时间哦~

今日一言

- -
加载中...
换一句

标签TAG

热评文章