python如何判斷單向鏈表是否包括環

這篇文章主要介紹了python如何判斷單向鏈表是否包括環，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

關于數據結構相關的面試題，經常會問到鏈表中是否存在環結構的判斷，下圖就是存在環結構的鏈表。

那么如何判斷鏈表中是否存在環呢，下面解法的思路是采用快慢指針：

兩個指向頭節點的指針，fast和slow，一起從頭結點開始往后遍歷，fast每次移動兩個節點，slow每次移動一個節點，

這樣，如果存在環結構，那么fast指針在不斷繞環過程中，肯定會追上slow指針。

# -*- coding:utf-8 -*-
'''
Created on 2019年10月23日
@author: Administrator
'''
class Node(): #定義一個Node類，構造兩個屬性，一個是item節點值，一個是節點的下一個指向
  def __init__(self,item=None):
    self.item = item
    self.next = None
def findbeginofloop(head):#判斷是否為環結構并且查找環結構的入口節點
  slowPtr = head     #將頭節點賦予slowPtr
  fastPtr = head     #將頭節點賦予fastPtr
  loopExist =False    #默認環不存在，為False
  if head == None:    #如果頭節點就是空的，那肯定就不存在環結構
    return False
  while fastPtr.next != None and fastPtr.next.next != None:   #fastPtr的下一個節點和下下個節點都不為空
    slowPtr = slowPtr.next      #slowPtr每次移動一個節點
    fastPtr = fastPtr.next.next   #fastPtr每次移動兩個節點 
    if slowPtr == fastPtr :     #當fastPtr和slowPtr的節點相同時，也就是兩個指針相遇了
      loopExist = True
      print("存在環結構")
      break
  if loopExist == True:
    slowPtr = head
    while slowPtr != fastPtr:
      fastPtr = fastPtr.next
      slowPtr = slowPtr.next
    return slowPtr
  print("不是環結構")
  return False
if __name__ == "__main__":
  node1 = Node(1)
  node2 = Node(2)
  node3 = Node(3)
  node4 = Node(4)
  node5 = Node(5)
  node1.next = node2
  node2.next = node3
  node3.next = node4
  node4.next = node5
  node5.next = node2
  print(findbeginofloop(node1).item)

運行結果：

存在環結構
2

感謝你能夠認真閱讀完這篇文章，希望小編分享的“python如何判斷單向鏈表是否包括環”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!