快捷導(dǎo)航

python判斷單向鏈表是否包括環(huán)，若包含則計(jì)算環(huán)入口的節(jié)點(diǎn)實(shí)例分析

更新時(shí)間：2019年10月23日 11:48:50 作者：鯨落丶

這篇文章主要介紹了python判斷單向鏈表是否包括環(huán)，若包含則計(jì)算環(huán)入口的節(jié)點(diǎn),結(jié)合實(shí)例形式分析了Python針對單向鏈表的遍歷、判斷相關(guān)算法原理與使用技巧,需要的朋友可以參考下

本文實(shí)例講述了python判斷單向鏈表是否包括環(huán)，若包含則計(jì)算環(huán)入口的節(jié)點(diǎn)。分享給大家供大家參考，具體如下：

關(guān)于數(shù)據(jù)結(jié)構(gòu)相關(guān)的面試題，經(jīng)常會問到鏈表中是否存在環(huán)結(jié)構(gòu)的判斷，下圖就是存在環(huán)結(jié)構(gòu)的鏈表。

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

兩個(gè)指向頭節(jié)點(diǎn)的指針，fast和slow，一起從頭結(jié)點(diǎn)開始往后遍歷，fast每次移動兩個(gè)節(jié)點(diǎn)，slow每次移動一個(gè)節(jié)點(diǎn)，

這樣，如果存在環(huán)結(jié)構(gòu)，那么fast指針在不斷繞環(huán)過程中，肯定會追上slow指針。

# -*- coding:utf-8 -*-
'''
Created on 2019年10月23日
@author: Administrator
'''
class Node(): #定義一個(gè)Node類，構(gòu)造兩個(gè)屬性，一個(gè)是item節(jié)點(diǎn)值，一個(gè)是節(jié)點(diǎn)的下一個(gè)指向
  def __init__(self,item=None):
    self.item = item
    self.next = None
def findbeginofloop(head):#判斷是否為環(huán)結(jié)構(gòu)并且查找環(huán)結(jié)構(gòu)的入口節(jié)點(diǎn)
  slowPtr = head     #將頭節(jié)點(diǎn)賦予slowPtr
  fastPtr = head     #將頭節(jié)點(diǎn)賦予fastPtr
  loopExist =False    #默認(rèn)環(huán)不存在，為False
  if head == None:    #如果頭節(jié)點(diǎn)就是空的，那肯定就不存在環(huán)結(jié)構(gòu)
    return False
  while fastPtr.next != None and fastPtr.next.next != None:   #fastPtr的下一個(gè)節(jié)點(diǎn)和下下個(gè)節(jié)點(diǎn)都不為空
    slowPtr = slowPtr.next      #slowPtr每次移動一個(gè)節(jié)點(diǎn)
    fastPtr = fastPtr.next.next   #fastPtr每次移動兩個(gè)節(jié)點(diǎn) 
    if slowPtr == fastPtr :     #當(dāng)fastPtr和slowPtr的節(jié)點(diǎn)相同時(shí)，也就是兩個(gè)指針相遇了
      loopExist = True
      print("存在環(huán)結(jié)構(gòu)")
      break
  if loopExist == True:
    slowPtr = head
    while slowPtr != fastPtr:
      fastPtr = fastPtr.next
      slowPtr = slowPtr.next
    return slowPtr
  print("不是環(huán)結(jié)構(gòu)")
  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)

運(yùn)行結(jié)果：