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

成都服務器托管，創新互聯公司提供包括服務器租用、成都移動機房、帶寬租用、云主機、機柜租用、主機租用托管、CDN網站加速、申請域名等業務的一體化完整服務。電話咨詢：18982081108

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

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

兩個指向頭節點的指針，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如何判斷單向鏈表是否包括環”這篇文章對大家有幫助，同時也希望大家多多支持創新互聯成都網站設計公司，關注創新互聯成都網站設計公司行業資訊頻道，更多相關知識等著你來學習!

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、網站設計器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

文章標題：python如何判斷單向鏈表是否包括環-創新互聯
本文路徑：http://m.newbst.com/article36/dpidpg.html

成都網站建設公司_創新互聯，為您提供做網站、電子商務、搜索引擎優化、商城網站、App開發、網站策劃

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯