快捷導(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中not 與 is None的區(qū)別
這篇文章主要介紹了在python中not 與 is None的區(qū)別，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2021-05-05
Python命名空間的本質(zhì)和加載順序
這篇文章主要介紹了Python命名空間的本質(zhì)和加載順序，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2018-12-12
Python3.6日志Logging模塊簡(jiǎn)單用法示例
這篇文章主要介紹了Python3.6日志Logging模塊簡(jiǎn)單用法,結(jié)合實(shí)例形式分析了Python3.6環(huán)境下日志Logging模塊設(shè)置格式、文件流輸出相關(guān)操作技巧,需要的朋友可以參考下
2018-06-06
Python的Pillow庫(kù)進(jìn)行圖像文件處理（圖文詳解）
本文詳解的講解了使用Pillow庫(kù)進(jìn)行圖片的簡(jiǎn)單處理，使用PyCharm開(kāi)發(fā)Python的詳細(xì)過(guò)程和各種第三方庫(kù)的安裝與使用。感興趣的可以了解一下
2021-11-11
利用Python實(shí)現(xiàn)kNN算法的代碼
這篇文章主要介紹了利用Python實(shí)現(xiàn)kNN算法的代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2019-08-08
Python 實(shí)現(xiàn)隨機(jī)數(shù)詳解及實(shí)例代碼
這篇文章主要介紹了Python 實(shí)現(xiàn)隨機(jī)數(shù)詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
2017-04-04
Python實(shí)現(xiàn)文件按照日期命名的方法
這篇文章主要介紹了Python實(shí)現(xiàn)文件按照日期命名的方法,涉及Python針對(duì)文件的遍歷、讀寫(xiě)及時(shí)間操作相關(guān)技巧,需要的朋友可以參考下
2015-07-07
Python+Pygame實(shí)現(xiàn)接小彈珠游戲
這篇文章主要為大家詳細(xì)介紹了Python如何利用Pygame實(shí)現(xiàn)接小彈珠游戲，即用擋板接住會(huì)反彈的小球，隨著次數(shù)的增多，速度變快，分?jǐn)?shù)增多，感興趣的可以了解一下
2022-12-12
pycocotools介紹以及在windows10下的安裝過(guò)程
這篇文章主要介紹了pycocotools介紹以及在windows10下的安裝過(guò)程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2023-02-02
對(duì)python cv2批量灰度圖片并保存的實(shí)例講解
今天小編就為大家分享一篇對(duì)python cv2批量灰度圖片并保存的實(shí)例講解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2018-11-11