Python判断链表是否有环：快慢指针法实现

快慢指针法原理

判断链表是否有环，最直观的方法是使用集合记录访问过的节点，但空间复杂度为O(N)。更优的解法是快慢指针法（Floyd判圈算法）：设置两个指针，一个每次移动一步（慢指针），另一个每次移动两步（快指针）。如果链表存在环，快指针最终会追上慢指针；如果不存在环，快指针会先到达链表末尾。

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()

代码逻辑解析

在LinkList类中，append方法用于从尾部添加元素。特别地，当添加值为4的节点时，代码手动将node.next指向self.head，从而在链表中制造一个环（1->2->3->4->1...）。这是为了测试hasCycle方法而设计的示例逻辑。

hasCycle方法接收链表头节点，初始化slow和fast指针均指向头节点。在while循环中，slow每次移动一步，fast每次移动两步。如果slow与fast指向同一节点（slow is fast），则说明存在环，返回True；若循环结束仍未相遇，则返回False。

测试与验证

在main函数中，我们创建了一个LinkList实例，依次添加节点1、2、3、4。由于添加节点4时触发了成环逻辑，链表结构变为有环链表。调用l.hasCycle(head)将输出True，验证了快慢指针法的有效性。

注意：在实际生产环境中，链表通常由外部数据源构建，不会像示例中那样手动制造环。此代码主要用于算法演示和学习。

以上就是Python判断链表是否有环的详细内容，更多关于Python链表算法的资料请关注本站其它相关文章！