python中什么相當于鏈表，python 單鏈表是否有回路_（Python3）數據結構--單鏈表之判斷鏈表是否有環

前言

有Python基礎

python中什么相當于鏈表，有數據結構單鏈表基礎，沒接觸過的可以看下面鏈接

https://blog.csdn.net/sf9898/article/details/104946291

原理和實現

python如何新建一個文本文檔，有一個鏈表，但是我們不知道這個鏈表是否內部有形成一個環(形成回路)，因此需要有一個函數來檢測是否有環(由此可知，這個函數的返回值應是布爾型)。

先去繼承一下單鏈表的螞蟻花唄(屬性和方法)，詳見鏈接：https://blog.csdn.net/sf9898/article/details/104946291 將單鏈表的定義拷貝下來。

直接可以做測試，構建一個鏈表(或許有環，這一部分先寫沒環的)，代碼如下：

python單鏈表的創建、ll = Link()

# 先構建測試用的鏈表

for i in range(5):

python逐行讀取文本文件？ll.addFront(i)

ll.addFront(100)

ll.addBack(250)

給定一個鏈表。for i in range(5):

ll.addBack(i)

# 到目前為止是一串沒有環的鏈表

判斷其中是否有環？ll.travel() # 100 4 3 2 1 0 250 0 1 2 3 4

在代碼中加入了幾個明顯與其他成員格格不入的data，這樣子也更容易區分下。

接下來構建有環的鏈表，設置一個函數getLastNode使得我們可以取到鏈表的最后一個節點(這個例子中就是4這個節點)，然后將它的next指向250的這個節點(又要有個函數能夠取到這個節點，因此有了getNode這個函數)，這樣就可以形成環了。效果大致如下圖。

# class Link的方法

def getLastNode(self):

cur = self.__head

pre = None

while cur:

pre = cur

cur = cur.next

return pre

def getNode(self, item):

cur = self.__head

res = None

while cur:

if cur.item == item:

res = cur

break

else:

cur = cur.next

return res

ll = Link()

# 先構建測試用的鏈表

for i in range(5):

ll.addFront(i)

ll.addFront(100)

ll.addBack(250)

for i in range(5):

ll.addBack(i)

# 到目前為止是一串沒有環的鏈表

ll.travel() # 100 4 3 2 1 0 250 0 1 2 3 4

# 接下來構建有環的鏈表

# 設置一個函數getLastNode使得我們可以取到鏈表的最后一個節點(這個例子中就是4這個節點)，

# 然后將它的next指向250的這個節點(又要有個函數能夠取到這個節點，因此有了getNode這個函數)，這樣就可以形成環了

# print(ll.getNode(250).item) # 這一行用來驗證getNode 函數的正確性，應打印250

ll.getLastNode().next = ll.getNode(250)

ll.travel() # 事實上現在遍歷一下就可以發現事情不簡單了

既然是要寫一個函數來判斷，那建議還是將這個函數寫成class Link的方法。

def hasLoop(self):

if self.__head is None:

return False

# 能到這說明頭結點不是空的，但是有可能只有一個節點，也有可能 N個(N > 1)

aNode = self.__head

bNode = self.__head

res = False

# 2個結點，往前跑，一個跑的快，一個跑的慢，如果沒有環，慢的結點不會追上快的

# 如果有環，肯定有一個時刻，快的點繞回來追上了慢的點

# 如果只有一個或兩個結點，則不會進行下面的循環，直接返回False (res)

while bNode.next and bNode.next.next:

bNode = bNode.next.next # 這里用B結點代表跑的快的，A是跑的慢的

aNode = aNode.next

if bNode == aNode:

res = True

break

return res

測試一下，完整代碼：

class Node(object):

def __init__(self, item):

self.item = item

self.next = None

class Link(object):

def __init__(self):

self.__head = None

def isEmpty(self):

return self.__head is None

# 頭部插入

def addFront(self, item):

node = Node(item)

node.next = self.__head

self.__head = node

# 尾部插入

def addBack(self, item):

node = Node(item)

if self.__head is None:

self.__head = node

return

cur = self.__head

pre = None

while cur:

pre = cur

cur = cur.next

# 當cur 為最后一個節點時帶入，pre更新為最后一個節點，cur更新為最后一個節點的下一個節點即為空，

# 下一次while cur 時會退出循環，此時的pre表示的就是最后一個節點，將node掛到pre的后面即可

pre.next = node

def size(self):

count = 0

cur = self.__head

while cur:

count += 1

cur = cur.next

return count

def travel(self):

cur = self.__head

while cur:

print(cur.item, end=' ')

cur = cur.next

print('')

# 刪除頭部節點

def removeFront(self):

cur = self.__head

self.__head = self.__head.next

cur.next = None

# 刪除尾部節點

def removeBack(self):

# 空節點時

if self.__head is None:

return

# 只有一個節點

if self.__head and self.__head.next is None:

self.__head = None

return

# 鏈表節點有兩個及以上

cur = self.__head # 當前節點

pre = None # 前一個節點

cn = cur.next # 后一個節點

# 剛開始cur取到的是第一個節點，cn是第二個

while cn:

pre = cur

cur = cur.next

cn = cur.next

pre.next = None

def getLastNode(self):

cur = self.__head

pre = None

while cur:

pre = cur

cur = cur.next

return pre

def getNode(self, item):

cur = self.__head

res = None

while cur:

if cur.item == item:

res = cur

break

else:

cur = cur.next

return res

def hasLoop(self):

if self.__head is None:

return False

# 能到這說明頭結點不是空的，但是有可能只有一個節點，也有可能 N個(N > 1)

aNode = self.__head

bNode = self.__head

res = False

# 2個結點，往前跑，一個跑的快，一個跑的慢，如果沒有環，慢的結點不會追上快的

# 如果有環，肯定有一個時刻，快的點繞回來追上了慢的點

# 如果只有一個或兩個結點，則不會進行下面的循環，直接返回False

while bNode.next and bNode.next.next:

bNode = bNode.next.next # 這里用B結點代表跑的快的，A是跑的慢的

aNode = aNode.next

if bNode == aNode:

res = True

break

return res

ll = Link()

# 先構建測試用的鏈表

for i in range(5):

ll.addFront(i)

ll.addFront(100)

ll.addBack(250)

for i in range(5):

ll.addBack(i)

# 到目前為止是一串沒有環的鏈表

ll.travel() # 100 4 3 2 1 0 250 0 1 2 3 4

# 接下來構建有環的鏈表

# 設置一個函數getLastNode使得我們可以取到鏈表的最后一個節點(這個例子中就是4這個節點)，

# 然后將它的next指向250的這個節點(又要有個函數能夠取到這個節點，因此有了getNode這個函數)，這樣就可以形成環了

# print(ll.getNode(250).item) # 這一行用來驗證getNode 函數的正確性，應打印250

ll.getLastNode().next = ll.getNode(250)# 注釋掉這行，就無法形成環了，這時下面的打印結果應是False

# ll.travel() # 事實上現在遍歷一下就可以發現事情不簡單了

print(ll.hasLoop())

結果

后面發現這樣其實是不嚴謹的，當節點數為2的時候，并且第二個node的next指向第一個，這個時候也算是一個環，在上面的代碼中吧這種情況當做不是環。為了實現這個要求，需要對上面的代碼進行修改。

def hasLoop(self):

if self.__head is None:

return False

# 能到這說明頭結點不是空的，但是有可能只有一個節點，也有可能 N個(N > 1)

if self.__head and self.__head.next is None:

# 只有一個頭結點，不認為是環

return False

# 能到這里就說明，至少有2個節點了

# 有兩個及以上結點，這里第二個節點的next指向None可以說明沒有環，否則這里就有可能會出現環

if self.__head.next.next == self.__head:

# 如果第二個節點的next指向第一個節點則認為是環，否則可能是指向空或者是下一個節點

return True

aNode = self.__head

bNode = self.__head

res = False

# 設置2個結點，往前跑，一個跑的快，一個跑的慢，如果沒有環，慢的結點不會追上快的

# 如果有環，肯定有一個時刻，快的點繞回來追上了慢的點

# 如果只有兩個結點(也就是說第二個節點的next指向None)，則不會進行下面的循環，直接返回False

while bNode.next and bNode.next.next:

bNode = bNode.next.next # 這里用B結點代表跑的快的，A是跑的慢的

aNode = aNode.next

if bNode == aNode:

res = True

break

return res

完整代碼：

class Node(object):

def __init__(self, item):

self.item = item

self.next = None

class Link(object):

def __init__(self):

self.__head = None

def isEmpty(self):

return self.__head is None

# 頭部插入

def addFront(self, item):

node = Node(item)

node.next = self.__head

self.__head = node

# 尾部插入

def addBack(self, item):

node = Node(item)

if self.__head is None:

self.__head = node

return

cur = self.__head

pre = None

while cur:

pre = cur

cur = cur.next

# 當cur 為最后一個節點時帶入，pre更新為最后一個節點，cur更新為最后一個節點的下一個節點即為空，

# 下一次while cur 時會退出循環，此時的pre表示的就是最后一個節點，將node掛到pre的后面即可

pre.next = node

def size(self):

count = 0

cur = self.__head

while cur:

count += 1

cur = cur.next

return count

def travel(self):

cur = self.__head

while cur:

print(cur.item, end=' ')

cur = cur.next

print('')

# 刪除頭部節點

def removeFront(self):

cur = self.__head

self.__head = self.__head.next

cur.next = None

# 刪除尾部節點

def removeBack(self):

# 空節點時

if self.__head is None:

return

# 只有一個節點

if self.__head and self.__head.next is None:

self.__head = None

return

# 鏈表節點有兩個及以上

cur = self.__head # 當前節點

pre = None # 前一個節點

cn = cur.next # 后一個節點

# 剛開始cur取到的是第一個節點，cn是第二個

while cn:

pre = cur

cur = cur.next

cn = cur.next

pre.next = None

def getLastNode(self):

cur = self.__head

pre = None

while cur:

pre = cur

cur = cur.next

return pre

def getNode(self, item):

cur = self.__head

res = None

while cur:

if cur.item == item:

res = cur

break

else:

cur = cur.next

return res

def hasLoop(self):

if self.__head is None:

return False

# 能到這說明頭結點不是空的，但是有可能只有一個節點，也有可能 N個(N > 1)

if self.__head and self.__head.next is None:

# 只有一個頭結點，不認為是環

return False

# 能到這里就說明，至少有2個節點了

# 有兩個及以上結點，這里第二個節點的next指向None可以說明沒有環，否則這里就有可能會出現環

if self.__head.next.next == self.__head:

# 如果第二個節點的next指向第一個節點則認為是環，否則可能是指向空或者是下一個節點

return True

aNode = self.__head

bNode = self.__head

res = False

# 設置2個結點，往前跑，一個跑的快，一個跑的慢，如果沒有環，慢的結點不會追上快的

# 如果有環，肯定有一個時刻，快的點繞回來追上了慢的點

# 如果只有兩個結點(也就是說第二個節點的next指向None)，則不會進行下面的循環，直接返回False

while bNode.next and bNode.next.next:

bNode = bNode.next.next # 這里用B結點代表跑的快的，A是跑的慢的

aNode = aNode.next

if bNode == aNode:

res = True

break

return res

ll = Link()

# # 先構建測試用的鏈表

# for i in range(5):

# ll.addFront(i)

# ll.addFront(100)

# ll.addBack(250)

# for i in range(5):

# ll.addBack(i)

# # 到目前為止是一串沒有環的鏈表

# ll.travel() # 100 4 3 2 1 0 250 0 1 2 3 4

# # 接下來構建有環的鏈表

# # 設置一個函數getLastNode使得我們可以取到鏈表的最后一個節點(這個例子中就是4這個節點)，

# # 然后將它的next指向250的這個節點(又要有個函數能夠取到這個節點，因此有了getNode這個函數)，這樣就可以形成環了

#

# # print(ll.getNode(250).item) # 這一行用來驗證getNode 函數的正確性，應打印250

#

# # ll.getLastNode().next = ll.getNode(250)

# # ll.travel() # 事實上現在遍歷一下就可以發現事情不簡單了

# print(ll.hasLoop())

# 一種特殊的情況，只有兩個結點，但是形成環

ll.addBack(1)

ll.addBack(2)

ll.getLastNode().next = ll.getNode(1)

print(ll.hasLoop())# 現在結果應該是True

結果