精华内容
下载资源
问答
  • 寻找链表中的环
    2020-10-12 12:41:32

    1、先判断是否有环

    **思路:**用快慢两个指针分别从链表头开始,慢指针 -> next,快指针 -> next -> next,这样如果有环那快指针务必会跑到慢指针后面,随即两者之间的距离一次会缩小一步,最终相遇。若是未相遇且快指针的 next 为 null,则说明链表无环。

    2、若是有环怎么找到环入口

    链表中有闭环即快慢两指针相遇了
    在这里插入图片描述
    当两指针在 P 点相遇,我们可列出如下等式:

    2(L+x) = L+x+n*H        (n >= 1) // n 为快指针在闭环上的圈数
    => 2L+2x = L+x+n*H      (n >= 1)
    => L = n*H-x            (n >= 1)
    => L = (n-1)*H+(H-x)   (n >= 1)
    

    思路: 当 l1 与 l2 相遇时,再来一个 l3 指针从链表头开始,而 l1 继续走,l2 就可以终结其使命没必要继续走了。此时 l1 和 l3 指针都是指向其 next。当 l3 指针到达环入口时,l1 也必然到达了环入口,即 l1 和 l3 指针会在环入口相遇,从而可求得入口位置。

    更多相关内容
  • 寻找链表中环的入口结点主要分成三个步骤: 首先是设置两个快慢指针,如果快慢指针相遇,则快慢指针必然都在环中; 然后从相遇的地方设置一个指针向后遍历并记录走的步数,当这个指针重新指到开始的位置的时候,当前...
  • 循环链表和约瑟夫 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的...
  • 感谢二符号四字母老师提供的题目,上传留念一下
  • js代码-寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常...
  • 寻找链表环的入口

    万次阅读 多人点赞 2019-06-11 16:53:12
    寻找链表环的入口) 题解: 这个连同I都是很经典的题啦,刷CC150时候就折磨了半天。 其实就推几个递推公式就好。。首先看图(图引用自CC150): 从链表起始处到环入口长度为:a,从环入口到Faster和Slower相遇点...

    (寻找链表环的入口)
    题解:

    这个连同I都是很经典的题啦,刷CC150时候就折磨了半天。

    其实就推几个递推公式就好。。首先看图(图引用自CC150):
    在这里插入图片描述
    从链表起始处到环入口长度为:a,从环入口到Faster和Slower相遇点长度为:x,整个环长为:c。

    明确了以上信息,就可以开始做运算了。。

    假设从开始到相遇,Slower走过的路程长为s,由于Faster的步速是Slower的2倍,那么Faster在这段时间走的路程长为2s。

    而对于Faster来说,他走的路程还等于之前绕整个环跑的n圈的路程nc,加上最后这一次遇见Slower的路程s。

    所以我们有:

                   2s = nc + s 
    

    对于Slower来说,他走的路程长度s还等于他从链表起始处到相遇点的距离,所以有:

                    s = a + x 
    

    通过以上两个式子代入化简有:

                    a + x = nc
    
                    a = nc - x
    
                    a = (n-1)c + c-x
    
                    a = kc + (c-x)
    

    那么可以看出,c-x,就是从相遇点继续走回到环入口的距离。上面整个式子可以看出,如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走(都只迈一步),那么绕过k圈以后, pointer2会和pointer1在环入口相遇。这样,换入口就找到了。

     //找到链表中环的入口点
        public static Node findLoopPort(Node head){
            //首先判断头结点是否为null
            if(head==null||head.next==null)
                return null;
            Node fast = head,slow=head;
            //找到相遇点fast
            while (true) {
                if (fast == null || fast.next == null) {
                    return null;
                }
                //找到
                slow = slow.next;
                fast = fast.next.next;
    
                if(fast == slow)
                    break;
            }
            //相遇点与链表头分别设定一个指针,每次各走一步,相遇第一个点即为环入口点
            slow = head;//slow back to start point
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow; //when slow == fast, it is where cycle begins
        }
        @Test
        public void testIsLoop() {
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            Node n4 = new Node(4);
            Node n5 = new Node(5);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
            n5.next = n2;  //构造一个带环的链表,去除此句表示不带环
            boolean b = LinkedList.IsLoop(n1);
            System.out.println(b);//true
    
            Node loopPort = LinkedList.findLoopPort(n1);
            System.out.println(loopPort.data);
        }
    

    在这里插入图片描述

    展开全文
  • 2-11寻找链表中

    2020-02-29 16:03:04
    传入一个头节点判断链表是否有,如果有返回第一个入的节点,如果没有返回null。 解题方法1 可以使用哈希表来完成,每遍历一个节点就把该节点的引用存储到哈希表,如果哈希表出现了重复的引用,那么那个...

    题目描述

    • 传入一个头节点判断链表是否有环,如果有环返回第一个入环的节点,如果没有环返回null。

    解题方法1

    • 可以使用哈希表来完成,每遍历一个节点就把该节点的引用存储到哈希表,如果哈希表中出现了重复的引用,那么那个重复的引用就是第一个入环的节点。如果没有出现重复的引用说明没有环。
    public class Test {
        public static void main(String[] args) throws Exception {
             int[] arr1 = {2,3,4,5};
             Node head1 = create1(arr1);
             Node head2 = create2(arr1);
             Node n1 = ishuan(head1);
             Node n2 = ishuan(head2);
            System.out.println(n1);
            System.out.println(n2.val);
        }
        //判断链表是否有环
        public static Node ishuan(Node head){
            HashSet<Node> set = new HashSet<>();
            for(Node p=head.next;p!=null;p=p.next){
                if(set.contains(p)){
                    return p;
                }
                else{
                    set.add(p);
                }
            }
            return null;
        }
        //创建一个无环单链表
        public static Node create1(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            return head;
        }
        //创建一个有环单链表
        public static Node create2(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            lastnode.next = head.next; //这里让尾节点指向第一个节点
            return head;
        }
    }
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    
    • 算法的时间复杂度为n,空间复杂度为n。

    解题方法2

    • 我们可以使用快慢指针法进行优化,使得空间复杂度为1。
    • 定义一个慢指针slow一个快指针fast,慢指针每次移动一步,快指针每次移动两步。如果无环快指针会首先到达终点,如果有环快慢指针会相遇。
    • 需要注意的是,我们不仅要判断它是否有环,还要找出第一个入环的节点。这个寻找的过程还是比单纯判断是否有环麻烦一点。
    • 首先让两个指针都指向第一个节点,然后分别移动两个指针,当快指针到达终点说明无环返回null。
    • 当快指针和慢指针再一次相遇说明有环。此时将快指针指向第一个节点,并改为一次移动一步,慢指针照常移动,那么下次两指针相遇的地方就是第一个入环的节点。
    • 证明如下:设链表无环部分长度为a,有环部分长度为b,两指针第一次相遇的位置距离入环口为x。
      在这里插入图片描述
    • 如,上图可以证明a = b-x。那么当两指针在x处相遇时慢指针再走b-x的距离可以到达环口且链表初始点距离环口为a,此时把快指针指向开头并调整速度为1由于a = b-x,那么它们必然会在环口相遇。
    • 代码如下
    public class Test {
        public static void main(String[] args) throws Exception {
             int[] arr1 = {2,3,4};
             Node head1 = create1(arr1);
             Node head2 = create2(arr1);
             Node n1 = ishuan(head1);
             Node n2 = ishuan(head2);
            System.out.println(n1);
            System.out.println(n2.val);
        }
        //判断链表是否有环
        public static Node ishuan(Node head){
            Node slow = head.next;
            Node fast = head.next;
            int i = 0;
            //第一次循环 如果无环返回null
            while (slow!=null&&fast!=null){
                if(fast.next==null){
                    return null;
                }
                if(i>0 && slow==fast){
                    break;
                }
                fast = fast.next.next;
                slow = slow.next;
                i++;
            }
            if(fast==null){
                return null;
            }
            //第二次循环 调整fast指针 寻找入环口节点并返回
            fast = head.next;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        //创建一个无环单链表
        public static Node create1(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            return head;
        }
        //创建一个有环单链表
        public static Node create2(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            lastnode.next = head.next; //这里让尾节点指向第一个节点
            return head;
        }
    }
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    
    展开全文
  • 普歌-链表java

    2022-05-18 15:27:02
    链表

    链表找环

    在这里插入图片描述

    思路

    创建两个指针1和2(两个对象引用),同时指向这个链表的头节点。
    首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

    java代码

    public boolean isPalindrome(ListNode head) {
           ListNode fast = head;
           ListNode slow = head;
    
           while(true){
               if (fast != null && fast.next != null && slow !=null){
                   fast = fast.next.next;
                   slow = slow.next;
                   if (fast == slow){
                       return true;
                   }
               }else {
                   return false;
               }
           }
        }
    

    • 作者:麦克猫Cat
    • 本文版权归作者和CSDN共有,欢迎交流
    展开全文
  • 假如一个链表中存在,那么可以利用哈希法和双指针法来判断是否存在,同时,利用三指针就可以找到的入口位置
  • 给出一个链表,如果其中有,则需找出的入口节点:即从头结点开始遍历,第一个被访问到的环中的节点。 如下图示,入口节点的值为 2。 方法一:双指针;分析距离 当一个链表时,快慢指针必然会进入到环中。...
  • 力扣练习,判断链表中是否有
  • 1.如何判断链表是否有 通过快慢指针来判断是否有,慢指针每次行走1步,快指针每次走2步,如果快指针等于慢指针说明有,如果快指针为空说明没有。 static bool judge(Point P) { if (P == null) return ...
  • 我们先来了解一下查找链表入口点常用的方法。 即使用快慢指针来解决该问题 public Entry loopEntry(){ if(headEntry == null || headEntry.next == null){ return null; } if(headEntry.next == ...
  • 代码题--C++--判断单链表其中是否有寻找链表结点 题目:给定一个单链表,(1)判断其中是否有,(2)寻找链表结点。 1.判断时候有(链表头指针为head) 对于这个问题我们可以采用“快慢指针”的...
  • js代码-FindFirstNodeJS 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常...
  • 快指针fast走两步,慢指针slow走一步,如果相遇就是带环链表; 然后让cur1从链表头开始走,cur2从相遇点开始走,再次相遇的位置就是入的第一点 public class DateCycle { static class ListNode { int val; ListNode...
  • 结论:假设快指针fast与慢指针slow在环中相遇时所指向的节点为meet,则一个指针从meet开始走,另一个指针从head开始走,两个指针必定在链表开始入的节点begin 处相遇。 证明如下: 假设链表中环总长度为C,从...
  • 题目描述:给你一个链表的头节点 head ,判断链表中是否有。 方法一:使用List集合(简单) 思路:从头到尾遍历链表,如果链表里面没有该节点,把该节点存放在List集合;当链表遍历完的时候,所有节点都放在...
  • 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 Id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常消息即可。
  • 环形链表的起点

    2021-09-24 12:40:12
    解释:链表中有一个,其尾部连接到第二个节点。 解题思路: 1、使用快慢指针,先判断是否有 快指针每一次走两步,慢指针一次走一步。 如果链表存在,那么快指针与慢指针一定会在环中某个位置相遇。 2、若存在...
  • 刷题日记-链表中

    2022-07-06 10:04:29
    判断链表中是否有 链表中的入环节点 两链表的交点
  • java代码-寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 Id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常...
  • 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常消息即可。
  • 寻找链表环的问题

    千次阅读 2018-04-12 19:20:07
    寻找链表环的问题 一、简介 这篇博客主要介绍判断链表是否存在环、寻找环的入口点和计算链表的长度的解决方案,主要是介绍思想,不涉及代码。(因为本萌新的师傅一直教育思想的重要性) 这里主要介绍三种解决...
  • https://leetcode.cn/problems/linked-list-cycle-ii/submissions/
  • 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 Id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常消息即可。
  • /*:在一个单链表存在一个循环子链表,有两种解题思路 思路一:从当前head出发,每前进一步就往回比较所有前驱节点,看是否是相同节点,若是则存在、 思路二:定义快慢指针,快指针每次走两步,慢指针每次走...
  • 如何判断链表

    2020-01-17 17:29:50
    有一个单向链表链表当中有可能出现“”,就像题图这样。如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。方法一、穷举遍历 方法一:首先从头节点开始,依次遍历...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,737
精华内容 6,294
热门标签
关键字:

寻找链表中的环