当前位置: 首页 > 编程笔记 >

python判断链表是否有环的实例代码

琴宾鸿
2023-03-14
本文向大家介绍python判断链表是否有环的实例代码,包括了python判断链表是否有环的实例代码的使用技巧和注意事项,需要的朋友参考一下

先看下实例代码:

class Node:
  def __init__(self,value=None):
    self.value = value
    self.next = None

class LinkList:
  def __init__(self,head = None):
    self.head = head

  def get_head_node(self):
    """
    获取头部节点
    """
    return self.head
    
  def append(self,value) :
    """
    从尾部添加元素
    """  
    node = Node(value = value) 
    cursor = self.head 
    if self.head is None:
      self.head = node
    else:  
      while cursor.next is not None:
        cursor = cursor.next
    
 
      cursor.next = node
      if value==4:
        node.next = self.head
  
  def traverse_list(self):
    head = self.get_head_node()
    cursor = head
    while cursor is not None:
      print(cursor.value)
      cursor = cursor.next
    print("traverse_over") 
    
  def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    slow=fast=head
    while slow and fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast:
        return True
    return False
  

  
def main():
  l = LinkList()
  l.append(1)
  l.append(2)
  l.append(3)
  l.append(4)
  head = l.get_head_node()
  print(l.hasCycle(head))
  #l.traverse_list()


if __name__ == "__main__":
  main()

知识点思考:

判断一个单链表是否有环,

可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.

其实 可以遍历这个单链表, 访问过后,

如果这个节点 不在 set 里面, 把这个节点放入到 set 集合里面.

如果这个节点在 set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环

如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

以上就是本次介绍的全部相关知识点内容,感谢大家的学习和对小牛知识库的支持。

 类似资料:
  • 本文向大家介绍如何判断单链表是否是循环链表?相关面试题,主要包含被问及如何判断单链表是否是循环链表?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 时间复杂度:O(n) 空间复杂度:O(1) 两个指针,一个每次走一步,一个每次走两步,如果有环,两者会相遇。相遇后,让一个指针从头结点再次出发,两个指针每次都走一步,直到相遇点即为环入口。 Java 代码示例:

  • 本文向大家介绍算法题,单链表判断是否有环(leetcode easy),以及判断环入口相关面试题,主要包含被问及算法题,单链表判断是否有环(leetcode easy),以及判断环入口时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 是否有环: 判断环入口:  

  • 本文向大家介绍请问如何判断一个链表是否有环?相关面试题,主要包含被问及请问如何判断一个链表是否有环?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 方法1:用一个指针数组A,存储已访问过的节点。用一个指针p,每次在链表上移动一步,然后与指针数组A比较,若数组中没有指针与p相同,说明第一次访问p,将p放入数组中;若有指针与p相同,则存在环路,且第一次相同的节点就是环的入口点。 链表长度为n,

  • 本文向大家介绍Python判断变量是否是None写法代码实例,包括了Python判断变量是否是None写法代码实例的使用技巧和注意事项,需要的朋友参考一下 代码中经常会有变量是否为None的判断,有三种主要的写法: 第一种是`if x is None`; 第二种是 `if not x:`; 第三种是`if not x is None`(这句这样理解更清晰`if not (x is None)`)

  • 本文向大家介绍剑指offer之判断链表是否包含环,包括了剑指offer之判断链表是否包含环的使用技巧和注意事项,需要的朋友参考一下 1 问题 判断链表是否包含环 2 思路 2个指针,一个指针走一步,一个指针走2步,如果相遇则有,反之无。 3 代码实现 4 运行结果 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对呐喊教程的支持。如果你想了解更

  • 本文向大家介绍Python3实现的判断环形链表算法示例,包括了Python3实现的判断环形链表算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python3实现的判断环形链表算法。分享给大家供大家参考,具体如下: 给定一个链表,判断链表中是否有环。 方案一:快慢指针遍历,若出现相等的情况,说明有环 方案二:遍历链表,寻找.next=head的元素。 但超出时间限制 更多关于Pyth