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+浏览量

开启您的 职业生涯

完成课程获得认证

开始