Python 中的連結串列環

考慮我們有一個連結串列，我們需要檢查是否存在環。為了表示給定連結串列中的環，我們將使用一個名為 pos 的整數指標。這個 pos 代表了連結串列中尾部相連的位置。因此，如果 pos 為 -1，則連結串列中不存在環。例如，連結串列就像 [5, 3, 2, 0, -4, 7]，而 pos = 1。所以存在一個環，尾部與第二個節點相連。

為解決此問題，我們將按以下步驟進行 −

• 建立一個集合作為雜湊集合 H
• 當頭指標不為空 −
  • 如果雜湊集合 H 中存在頭指標，則返回 true
  • 將頭指標新增到雜湊集合 H 中
  • 頭指標 := 頭指標的下一個
• 返回 false

示例

讓我們看以下實現以更好地理解 −

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head
def get_node(head, pos):
   if pos != -1:
      p = 0
      ptr = head
      while p < pos:
         ptr = ptr.next
         p += 1
      return ptr
class Solution(object):
   def hasCycle(self, head):
      hashS = set()
      while head:
         if head in hashS:
            return True
         hashS.add(head)
         head = head.next
      return False
head = make_list([5,3,2,0,-4,7])
last_node = get_node(head, 5)
pos = 1
last_node.next = get_node(head, pos)
ob1 = Solution()
print(ob1.hasCycle(head))

輸入

List = [5,3,2,0,-4,7]
Pos = 1

輸出

True

Arnab Chakraborty

更新於: 28-Apr-2020

2K+瀏覽量

開啟您的 職業生涯

完成課程獲得認證

開始