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 里面,说明曾经访问过,所以这个链表有重新 走到了这个节点,因此一定有环

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!