Python 中的链表循环

pythonserver side programmingprogramming更新于 2025/10/31 14:04:17

假设我们有一个链表，我们必须检查是否存在循环。为了表示给定链表中的循环，我们将使用一个名为 pos 的整数指针。此 pos 表示链表中尾部连接的位置。因此，如果 pos 为 -1，则链表中不存在循环。例如，链表类似于 [5, 3, 2, 0, -4, 7]，pos = 1。因此存在一个循环，并且 tail 连接到第二个节点。

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

取一个集合作为哈希集 H
当 head 不为空时 −
- 如果 head 存在于 H 中，则返回 true
- 将 head 添加到 H
- head := next of head
返回 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))