Python中的链表循环

考虑我们有一个链表，我们必须检查是否有任何循环。为了表示给定链表中的循环，我们将使用一个称为pos的整数指针。此pos表示链接列表中连接了tail的位置。因此，如果pos为-1，则链表中没有循环。例如，链表类似于[5、3、2、0，-4、7]，而pos =1。所以有一个循环，尾部连接到第二个节点。

为了解决这个问题，我们将遵循以下步骤-

• 取一组作为哈希集H

• 而head不为null-

• 如果head存在于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