快捷導(dǎo)航

python判斷鏈表是否有環(huán)的實(shí)例代碼

更新時(shí)間：2020年01月31日 10:00:44 作者：一起來(lái)學(xué)python

在本篇文章里小編給大家整理的是關(guān)于python判斷鏈表是否有環(huán)的知識(shí)點(diǎn)及實(shí)例代碼，需要的朋友們參考下。

先看下實(shí)例代碼：

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):
    """
    獲取頭部節(jié)點(diǎn)
    """
    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()

知識(shí)點(diǎn)思考：

判斷一個(gè)單鏈表是否有環(huán),

可以用 set 存放每一個(gè) 節(jié)點(diǎn), 這樣每次訪問(wèn)后把節(jié)點(diǎn)丟到這個(gè)集合里面.

其實(shí) 可以遍歷這個(gè)單鏈表, 訪問(wèn)過(guò)后,

如果這個(gè)節(jié)點(diǎn) 不在 set 里面, 把這個(gè)節(jié)點(diǎn)放入到 set 集合里面.

如果這個(gè)節(jié)點(diǎn)在 set 里面 , 說(shuō)明曾經(jīng)訪問(wèn)過(guò), 所以這個(gè)鏈表有重新走到了這個(gè)節(jié)點(diǎn), 因此一定有環(huán)

如果鏈表都走完了, 把所有的節(jié)點(diǎn)都放完了. 還是沒(méi)有重復(fù)的節(jié)點(diǎn), 那說(shuō)明沒(méi)有環(huán).

以上就是本次介紹的全部相關(guān)知識(shí)點(diǎn)內(nèi)容，感謝大家的學(xué)習(xí)和對(duì)腳本之家的支持。

您可能感興趣的文章:

相關(guān)文章

Python實(shí)現(xiàn)批量生成,重命名和刪除word文件
這篇文章主要為大家詳細(xì)介紹了Python如何利用第三方庫(kù)實(shí)現(xiàn)批量生成、重命名和刪除word文件的功能，文中的示例代碼講解詳細(xì)，需要的可以參考一下
2023-03-03
OpenCV實(shí)現(xiàn)去除背景識(shí)別的方法總結(jié)
這篇文章主要為大家詳細(xì)介紹了如何利用OpenCV實(shí)現(xiàn)去除背景識(shí)別的功能，文中為大家總結(jié)了一些方法，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下
2022-10-10
python3.10及以上版本編譯安裝ssl模塊的詳細(xì)過(guò)程
最近搞安裝ssl模塊每天都弄到很晚,所以這里給大家整理下,這篇文章主要給大家介紹了關(guān)于python3.10及以上版本編譯安裝ssl模塊的詳細(xì)過(guò)程,文中介紹的非常詳細(xì),需要的朋友可以參考下
2023-05-05
Pyinstaller打包Pytorch框架所遇到的問(wèn)題
Pytorch在python界用得比較多,打包容易失敗，本文主要介紹了Pyinstaller打包Pytorch框架所遇到的問(wèn)題，文中介紹的十分詳盡，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03
python元組拆包實(shí)現(xiàn)方法
在本篇文章里小編給大家整理的是一篇關(guān)于python元組拆包實(shí)現(xiàn)方法及相關(guān)實(shí)例，有興趣的朋友們可以學(xué)習(xí)下。
2021-02-02
Python 3 使用Pillow生成漂亮的分形樹(shù)圖片
這篇文章主要介紹了Python 3 使用Pillow生成漂亮的分形樹(shù)圖片,本文通過(guò)實(shí)例代碼介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2019-12-12
Django渲染Markdown文章目錄的方法示例
這篇文章主要介紹了Django渲染Markdown文章目錄的方法示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2019-01-01
用Python編寫(xiě)個(gè)解釋器實(shí)現(xiàn)方法接受
計(jì)算機(jī)只能理解機(jī)器碼。歸根結(jié)底，編程語(yǔ)言只是一串文字，目的是為了讓人類更容易編寫(xiě)他們想讓計(jì)算機(jī)做的事情。真正的魔法是由編譯器和解釋器完成，它們彌合了兩者之間的差距。解釋器逐行讀取代碼并將其轉(zhuǎn)換為機(jī)器碼
2023-01-01
記一次django內(nèi)存異常排查及解決方法
這篇文章主要給大家介紹了關(guān)于一次django內(nèi)存異常排查記解決方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用django具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-08-08
Python基礎(chǔ)學(xué)習(xí)之反射機(jī)制詳解
在Python中，反射是指通過(guò)一組內(nèi)置的函數(shù)和語(yǔ)句，在運(yùn)行時(shí)動(dòng)態(tài)地訪問(wèn)、檢查和修改對(duì)象的屬性、方法和類信息的機(jī)制。本文將通過(guò)簡(jiǎn)單的示例和大家講講Python中的反射機(jī)制，希望對(duì)大家有所幫助
2023-03-03