精华内容
下载资源
问答
  • 分析:使用追赶的方法,设定两指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在,则两者相遇;如不存在,fast遇到NULL退出 class Solution: def hasCycle(self , head ): # write code here if...

    分析:使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出

    class Solution:
        def hasCycle(self , head ):
            # write code here
            if not head:
                return False
            node = head
            while node:
                noden = node.next
                if noden == head:
                    return True
                else:
                    node.next = head
                    node = noden
            return False
    
    展开全文
  • 最容易想到的办法就是遍历单链表,如果单链表有环的话那么会进入死循环,但是我们不知道单链表的长度,所以如果单链表长度很长,我们一直向下遍历,也无法分辨出是单链表还没遍历完还是进入了死循环。 所以这种解法...

    这是一个在我们学习数据结构的时候经常会遇到的问题,今天给大家带来这个问题的几种解法。

    方法一

    最容易想到的办法就是遍历单链表,如果单链表有环的话那么会进入死循环,但是我们不知道单链表的长度,所以如果单链表长度很长,我们一直向下遍历,也无法分辨出是单链表还没遍历完还是进入了死循环。

    所以这种解法不靠谱。

    方法二

    我们可以在遍历单链表中的每个元素的时候,每遍历一个新的节点,就从头再开始遍历一次已经遍历过的节点,用新节点和之前遍历过的节点相比较,如果新节点之前遍历过的节点相同,就说明单链表有环。

    单链表

    比如说已存在的单链表:A->B->C->D->E->F->G->D,在遍历到第七个节点(D)的时候,再在从头节点开始遍历到第三个节点,因为第三个集结点(D)和第七个节点相同,所以单链表一定有环。

    假设从单链表头节点到环入口节点的距离是D,单链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2,可以理解成O(N*N)。

    算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

    所以这个算法的时间复杂度是O(N*N),空间复杂度是O(1)。

    找环入口的话就很简单了,遍历到第一个判定单链表有环的节点(D)就是环的入口。

    方法三

    考虑到方法二每遍历一个新节点的时候都需要从头开始遍历遍历一遍节点,会导致时间复杂度很高,所以我们可以把已经遍历过的节点用一个HashSet存起来,然后每遍历一个新节点的时候再去和HashSet中的元素做匹配,如果HashSet中已存在该节点,那么单链表有环。

    假设从单链表头节点到环入口节点的距离是D,单链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1),所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。

    而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

    这个算法的时间复杂度是O(N),空间复杂度是o(N).

    找环入口和方法二一样,遍历到第一个判定单链表有环的节点(D)就是环的入口。

    方法四

    还有一种思路是创建两个变量slow和fast同时指向头节点,然后slow每次向后遍历一个节点,fast每次向后遍历两个节点,如果单链表没有环的话那么slow将永远追不上fast,而如果单链表有环的话slow就会追上fast。

    单链表2

    下面我们来模拟随着单链表的遍历slow和fast两个变量值的变化:

    次数\变量slowfast
    0AA
    1BC
    2CE
    3DG
    4EE
    5FG
    6GE
    7DG
    8EE

    单链表3

    可以看到遍历到第八次的时候,slow追上了fast,所以单链表有环。

    假设从单链表头节点到环入口节点的距离是D,单链表的环长是S。那么循环会进行S*K次,K为正整数,可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)。

    这个算法的时间复杂地是O(N),空间复杂度O(1)。

    那么如何找到环的入口呢?下面我们来进行一个小小的数学计算:设从单链表头节点到环入口节点的距离是D,环入口到相交点的距离是X,设slow和fast第一次相遇时fast走了n圈环,slow走的距离为len,那么fast走的距离是2*len,可以得出下面的两个等式:

    len = D + X
    2 * len = D + X + n * R

    两个等式相减可以的到:len = n * R - X

    通过这个等式我们可以再定义两个变量out和in,out指向单链表头节点,in指向之前slow和fast第一次相交的节点,out和in同时向后遍历,第一次相交的点就是环的入口。

    单链表4

    下面我们来模拟随着单链表的遍历out和in两个变量值的变化:

    次数\变量outin
    0AE
    1BF
    2CG
    3DD

    可以看到遍历到第三次的时候,out和in相遇在D节点,所以D节点时单链表的环入口。


    今天关于单链表是否有环以及环入口的问题就分享到这里了,提供了四种解法,第一种解法不太友好也不太合理,第二中解法时间复杂度太高,第三种解法空间复杂度太高,第四种解法可能时目前的最优解法了,希望对大家有所帮助。


    喜欢这篇文章的朋友,欢迎长按下图关注公众号lebronchen,第一时间收到更新内容。
    扫码关注

    展开全文
  •   如上图,最后一个节点指向了第三个节点,所以后面四个节点构成了一个环,怎么判断单链表是否有环呢?     一.快慢指针法判断有无:   1.算法思路:可以定义快慢指针(fast和slow),让fast每次步径是slow...

    什么是环?
      

      单链表有环,是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点,这样在链表的尾部形成一个环形结构。

    在这里插入图片描述
      如上图,最后一个节点指向了第三个节点,所以后面四个节点构成了一个环,怎么判断单链表是否有环呢?

    一.快慢指针法判断有无环:

      1.算法思路:可以定义快慢指针(fast和slow),让fast每次步径是slow的两倍,因为fast是两步两步走,所以注意循环条件(fast!=null && fast.next!=null),如果单链表有环,fast速度是slow的两倍,所以肯定会有一个时刻两个指针相遇,相遇即代表链表有环。
     (就和在操场上跑步的两个人一样,操场就代表着一个环,一个速度是另一个的两倍,速度快的肯定会有一个时刻追上速度慢的且处在同一个位置)


      2.参考代码:

    import java.util.List;
    
    class ListNode{
        public int data;
        public ListNode next;
    
    
        public ListNode(int data){
            this.data=data;
            this.next=null;
        }
    }//节点类
    
    class MySignalList {
        public ListNode head;
    
    
        public MySignalList() {
            this.head = null;
        }
    
        //尾插法
        public void addLast(int data) {
            ListNode node = new ListNode(data);
            if (this.head == null) {
                this.head = node;
            } else {
                ListNode cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
    
        }
    
    
        //人为创造一个环
        public void cycle(){
            ListNode cur=this.head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=this.head.next;
        }
    
        //有无环
        public boolean hasCycle(){
            ListNode fast=this.head;
            ListNode slow=this.head;
            while(fast!=null && fast.next!=null){
                slow=slow.next;         //slow每次走一步
                fast=fast.next.next;    //fast每次走两步
                if(slow==fast){         //判断两指针是否相遇
                    return true;
                }
            }
            return false;
        }
    }
    
    public class Test {
            public static void main(String[] args) {
                MySignalList my = new MySignalList();
                my.addLast(1);
                my.addLast(5);
                my.addLast(76);
                my.addLast(12);
                my.addLast(16);
                my.cycle();
                boolean i=my.hasCycle();
                if(i==true){
                    System.out.println("有环");
                }else{
                    System.out.println("没有环");
                }
    
            }
    }
    
    
    
    //打印结果
    有环
    
    



      

    二.判断环入口点

      1.算法思路:
           ①先找到快慢指针第一次相遇的位置
           ②把其中一个指针拉到链表头
           ③之后再让快慢指针一人一步走,再次相遇的点就是环的入口处

      2.原理如图:
    在这里插入图片描述
      假设链表总长为n,表头到环入口点距离为x,环入口点到第一次相遇的位置为y。因为fast速度是slow的两倍,所以fast走过的距离是slow的两倍
      即2(x+y)=n+y ----- n=2x+y,所以可得第一次相遇点到链表尾部距离也为x,将slow移到head位置,此时可以看到slow距离环的入口点距离为x,fast距离环的入口点距离也为x,两个距离环入口点距离相等,之后一人一步走,肯定会在环的入口点相遇。



      3.参考代码:

    public ListNode detectCycle(){
            ListNode fast=this.head;
            ListNode slow=this.head;
            //先找到第一次相遇的时候
            while(fast!=null && fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
                if(fast==slow){
                    break;
                }
            }
             if(fast==null || fast.next==null){
                return null;
            }
            //让slow或者fast到头那里
            slow=this.head;
            while(slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }
    
    展开全文
  • 用python 判断一个单链表是否有环

    千次阅读 2019-01-27 11:57:04
    用python 判断一个单链表是否有环. 思路1: 判断一个单链表是否有环, 可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面. 其实 可以遍历这个单链表, 访问过后, 如果这个节点 不在 set 里面, 把这...

    用python 判断一个单链表是否有环.

    https://leetcode.com/problems/linked-list-cycle/

    思路1:

    判断一个单链表是否有环,
    可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
    其实 可以遍历这个单链表, 访问过后,
    如果这个节点 不在 set 里面, 把这个节点放入到 set 集合里面.
    如果这个节点在 set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环
    如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    """
    @Time    : 2019/1/12 00:59
    @File    : has_circle.py
    @Author  : frank.chang@shoufuyou.com
    
    https://leetcode.com/problems/linked-list-cycle/
    
    
    141. Linked List Cycle
    Easy
    
    1231
    
    93
    
    Favorite
    
    Share
    Given a linked list, determine if it has a cycle in it.
    
    To represent a cycle in the given linked list,
    we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
    If pos is -1, then there is no cycle in the linked list.
    
    
    
    Example 1:
    
    Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the second node.
    
    
    Example 2:
    
    Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the first node.
    
    
    Example 3:
    
    Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.
    
    
    
    
    Follow up:
    
    Can you solve it using O(1) (i.e. constant) memory?
    
    Accepted
    340,579
    Submissions
    971,443
    
    """
    class LinkNode:
    
        def __init__(self, value):
            self.value = value
            self.next = None
    
    
    class Solution1:
        """
        思路分析:
        判断一个单链表是否有环,
        可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
        其实 可以遍历这个单链表, 访问过后,
        如果这个节点 不在 set  里面, 把这个节点放入到 set 集合里面.
        如果这个节点在  set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环.
    
        如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.
    
        """
    
        def hasCycle(self, head):
    
            mapping = set()
    
            flag = False
    
            p = head
    
            while p:
    
                if p not in mapping:
                    mapping.add(p)
                else:
                    flag = True
                    break
                p = p.next
    
            return flag
    

    还有一个解决方案:

    定义 两个指针, 一个快指针fast, 一个慢指针slow, 快指针一次走两步,慢指针一次走一步.
    如果 两个指针相遇了, 则说明链表是有环的.
    如果 fast 都走到null了, 还没有相遇则说明没有环.

    为什么是这样呢? 简单分析一下?
    图1

    图片2

    图片3

    图片4
    图片5

    图片6

    图片7
    用图形来分析一下,这样可以清晰一点.

    图形分析

    因为快指针 先走 所以快指针先进入环,之后慢指针后进入环, 无论如何,

    最后 要么 慢指针进入环的时候, 快指针可能已经走了 很多遍环, 也有可能没有走完环. 但无论如何 当慢指针 进入环的时候,
    fast 有可能在 慢指针的后面, 或者前面, 无论如何 快指针 是必慢指针走的快的 , 所以 只要有环 一定可以 和慢指针来一次相遇.

    你可能想 会不会错过呢?
    答案 是不会的. 你想 快指针一次 走两步, 慢指针一次都一步.
    假设 这是一条无穷尽的单链表. 他们 每走一步, 两者之间的距离就减1, 所以 只要链表足够长, 是一定会相遇的.

    看下图:
    图片8

    class Solution:
        """
        定义 两个指针, 一个快指针fast, 一个慢指针slow,  快指针一次都两步,慢指针一次走一步. 
        如果 两个指针相遇了, 则说明链表是有环的. 
        如果 fast 都走到null了, 还没有相遇则说明没有环. 
        """
    
        def hasCycle(self, head):
    
            flag = False
            if head is None or head.next is None or head.next.next is None:
                return flag
    
            fast = head.next.next
            slow = head.next
    
            while fast is not slow:
    
                if fast.next is None or fast.next.next is None:
                    # no circle
                    return flag
                fast = fast.next.next
                slow = slow.next
    
            # 相遇肯定有环
            if fast is slow:
                # hasCircle
                flag = True
    
            return flag
    

    第二次做DAY20201130

    闲下来 之前的代码 写的不够优雅,今天 重新修改了一下 之前的代码,这样写看起来 比 之前的代码 稍微 好看一点,详细请看下面

    141. 环形链表

    给定一个链表,判断链表中是否有环。

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    如果链表中存在环,则返回 true 。 否则,返回 false

    进阶:

    你能用 O(1)(即,常量)内存解决此问题吗?

    示例 1:

    img

    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。
    

    示例 2:

    img

    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。
    

    示例 3:

    img

    输入:head = [1], pos = -1
    输出:false
    解释:链表中没有环。
    

    提示:

    • 链表中节点的数目范围是 [0, 104]
    • -105 <= Node.val <= 105
    • pos-1 或者链表中的一个 有效索引

    方法1 路径记录法

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            visited = set() 
            while head:
                cur = head
                if cur not in visited:
                    visited.add(cur)
                else:
                    return True
                head = head.next 
            return False 
    
     
    class Solution02:
        def hasCycle(self, head: ListNode) -> bool:
            seen = set()
            while head:
                if head in seen:
                    return True
                seen.add(head)
                head = head.next
            return False
    
    

    方法2 快慢指针法

    第1种解法
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if not head:
                return False 
    
            slow = head 
            fast = head.next 
    
            while fast and fast.next:
                if fast ==slow:
                    return True 
                fast= fast.next.next 
                slow = slow.next 
                
            return False 
    
    另一种写法
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if head is None or  head.next is None:
                return False 
            
            slow = head 
            fast  =head.next 
            while slow != fast:    
                if fast is None or fast.next is None:
                    return False 
                fast = fast.next.next 
                slow = slow.next 
    
            return True 
    
    分享感动,留住快乐. 2019-01-27 11:53:45 --frank
    展开全文
  • 1.判断一个单链表是否存在 2.寻找的连接点 3.如何获取的长度 4.如何将带单链表变为普通的单链表 二.判断两个无环单链表是否相交 1.方法一 利用两个相交链表尾节点相等的属性 2.方法二 利用栈 3....
  • } } public static void main(String[] args) { /** * 造一个有环链表 */ LinkedNode l = new LinkedNode("!"); LinkedNode node = null; LinkedNode last = l; for(int i=0;i;i++){ LinkedNode temp = new ...
  • 题目:如何判断一个单链表是否有环?若有环,如何找出的入口节点。 一、单链表是否有环 思路分析: 单链表有环,是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点,这样在链表的尾部形成...
  • 顾名思义,有环单链表就是一个单链表中出现了一个环,但是这个比较特殊,它的位置很讲究。我们知道,单链表的结构为:而且在链表中,一个数据节点只能有一个前驱和一个后继,那么单链表
  • 引言:单链表是否有环是常见的笔试、面试题,也可能是解决其他方法的条路径。 ...1、如何判断单链表是否有环? 2、如何计算的长度? 3、如何找到入口节点? 4、如何计算该带单链表的长度?
  • C语言实现判断单链表是否有环

    千次阅读 2020-06-14 22:45:03
    C语言实现判断单链表是否有环 判断单链表是否存在的两种思路 计算步数 思路:定义两指针p,q,都指向头结点,p一直后移,q每次后移到和p相同的结点,判断p是否等于q,不等于则p继续后移,q重新头结点开始...
  • 给定一个单链表判断链表中是否有环。 题目背景 141. 环形链表——给定一个链表,判断链表中是否有环。 如果链表中某个节点,可以通过连续跟踪next指针再次到达,则链表中存在。 为了表示给定链表中的,...
  • 点击上方三分钟学前端,关注公众号回复交流,加入前端编程面试算法每日一题群面试官也在看的前端面试资料给定一个链表,判断链表中是否有环。为了表示给定链表中的,我们使用整数 pos 来表示链...
  • //将链表遍历的每节点的地址存储起来,遍历节点是与之匹配,若相同则说明链表有环; } int main() { int i; initlink(); printf("请插入数字构建单链表!\n"); for(i=0;i;i++) { ...
  • java判断单链表是否有环

    千次阅读 2019-03-26 12:31:55
    假设,现在有一个存在单链表。 // null->node1->node2->node3->node4->node5->node6->node1 对其进行分析,可以设置2个“指针”。 singleStep 每次向后 更新一个节点;doubleStep ...
  • 如何判断单链表是否有环? 2.如果有环,求出的入口 3.求长 4.求总长注意这里长度:节点的数量 链表定义参考:http://blog.csdn.net/dawn_after_dark/article/details/73610674探讨要想判断有环,我们可以...
  • 判断一个单链表是否存在

    千次阅读 2017-01-17 18:46:38
    #判断一个单链表是否存在 。 #设置两个指针(fast, slow),初始值都指向头,slow每次前进1步,fast每次前进2步, 大概的思路如下: 如果链表存在,则fast必定先进入,而slow后进入,两个指针必定相遇...
  • 检测单链表是否有环

    千次阅读 2019-03-11 17:48:03
    判断一个单链表是否有环的链接点(转) 给定一个单链表,只给出头指针h:&nbsp; 1、如何判断是否存在?&nbsp; 2、如何知道的长度?&nbsp; 3、如何找出的连接点在哪里?&nbsp; 4、带链表的...
  • 算法面试题:如何判断单链表是否存在

    万次阅读 多人点赞 2018-01-13 22:15:46
    一道算法面试题:判断单链表是否存在。 我们知道单链表中结点都是一个结点指向下一个结点这样一个一个链接起来的,直到尾结点的指针域没有指向,单链表就到此结束了。 这里存在的意思就是,尾结点的指针域并为...
  • 发布时间:2014-09-22 09:21:15有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一。问题:1、如何判断一个链表是不是这类链表?2、如果链表为存在,...
  • 判断一个单链表是否有环的链接点(转) 给定一个单链表,只给出头指针h: 1、如何判断是否存在? 2、如何知道的长度? 3、如何找出的连接点在哪里? 4、带链表的长度是多少? 解法: 1、对于...
  • 给定一个单链表,只给出头指针h: 1、如何判断是否存在? 2、如何知道的长度? 3、如何找出的连接点在哪里? 4、带链表的长度是多少?   解法: 1、对于问题1,使用追赶的方法,设定...
  • 如何判断单链表里面是否有环? 算法的思想是设定两个指针p, q,其中p每次向前移动一步,q每次向前移动两步。那么如果单链表存在,则p和q相遇;否则q将首先遇到null。 这里主要理解一个问题,就是为什么
  • 如何判断单链表有环及正确性证明

    万次阅读 多人点赞 2018-08-03 23:12:41
    给你一个单链表,需要找到一个方法进行判断是否有环的存在。这篇文章主要证明一下,为什么存在的情况下两个指针(slow和fast指针)就一定会相遇。 判断单链表是否有环 ​ 使用两个slow, fast指针从头开始扫描...
  • 判断一个单链表是否有环,如果,找出的起始位置。 分析: 我们可以从单链表head开始,每遍历一个,就把那个node放在hashset里,走到下一个的时候,把该node放在hashset里查找,如果相同的,就表示有环,...
  • 题目要求:给定一个单链表的头指针head,要求写一个函数判断这个单链表是否一个有环单链表单链表中的节点定义如下: struct listNode { int val; struct listNode *next; }; 方法1:首先定义一个map map,然后...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,437
精华内容 6,974
关键字:

判断一个单链表是否有环