Pythonのリンクリストサイクル

リンクリストがあり、サイクルがあるかどうかを確認する必要があるとします。指定されたリンクリストでサイクルを表すために、posと呼ばれる1つの整数ポインターを使用します。この位置は、テールが接続されているリンクリスト内の位置を表します。したがって、posが-1の場合、リンクリストにサイクルは存在しません。たとえば、リンクリストは[5、3、2、0、-4、7]のようで、pos =1です。したがって、サイクルがあり、テールは2番目のノードに接続されます。

これを解決するには、次の手順に従います-

• 1つのセットをハッシュセットHとして取得します
• ヘッドがnullでない場合-
  • ヘッドが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