python判斷單向鏈表是否包括環,若包含則計算環入口的節點實例分析

 更新時間:2019年10月23日 11:48:51   作者:鯨落丶   我要評論
這篇文章主要介紹了python判斷單向鏈表是否包括環,若包含則計算環入口的節點,結合實例形式分析了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相關內容感興趣的讀者可查看本站專題:《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程

希望本文所述對大家Python程序設計有所幫助。

相關文章

  • Python語言描述KNN算法與Kd樹

    Python語言描述KNN算法與Kd樹

    這篇文章主要介紹了Python語言描述KNN算法與Kd樹,具有一定借鑒價值,需要的朋友可以參考下。
    2017-12-12
  • python3+django2開發一個簡單的人員管理系統過程詳解

    python3+django2開發一個簡單的人員管理系統過程詳解

    這篇文章主要介紹了python3+django2開發一個簡單的人員管理系統過程詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07
  • Python使用pandas處理CSV文件的實例講解

    Python使用pandas處理CSV文件的實例講解

    今天小編就為大家分享一篇Python使用pandas處理CSV文件的實例講解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-06-06
  • Python中優化NumPy包使用性能的教程

    Python中優化NumPy包使用性能的教程

    這篇文章主要介紹了Python中優化NumPy包使用性能的教程,包括內存和拷貝等方面,需要的朋友可以參考下
    2015-04-04
  • 詳解Python網絡爬蟲功能的基本寫法

    詳解Python網絡爬蟲功能的基本寫法

    這篇文章主要介紹了Python網絡爬蟲功能的基本寫法,網絡爬蟲,即Web Spider,是一個很形象的名字。把互聯網比喻成一個蜘蛛網,那么Spider就是在網上爬來爬去的蜘蛛,對網絡爬蟲感興趣的朋友可以參考本文
    2016-01-01
  • 用Python搶火車票的簡單小程序實現解析

    用Python搶火車票的簡單小程序實現解析

    這篇文章主要介紹了用Python搶火車票的簡單小程序實現解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-08-08
  • Python采用Django開發自己的博客系統

    Python采用Django開發自己的博客系統

    這篇文章主要為大家詳細介紹了Python采用Django開發自己的博客系統,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-08-08
  • Python3 SSH遠程連接服務器的方法示例

    Python3 SSH遠程連接服務器的方法示例

    這篇文章主要介紹了Python3 SSH遠程連接服務器的方法示例,小編覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-12-12
  • Python解析并讀取PDF文件內容的方法

    Python解析并讀取PDF文件內容的方法

    這篇文章主要介紹了Python解析并讀取PDF文件內容的方法,結合實例形式分別描述了Python2.7在win32與win64環境下實現讀取pdf的相關操作技巧,需要的朋友可以參考下
    2018-05-05
  • Python里disconnect UDP套接字的方法

    Python里disconnect UDP套接字的方法

    這篇文章主要介紹了Python里disconnect UDP套接字的方法,本文使用的是ctypes繞過的方法,需要的朋友可以參考下
    2015-04-04

最新評論

2019开奖结果