アルゴリズム 体操21 LinkedList Cycle

LinkedList Cycle

上の画像のように、LinkedListが、サイクルであるかどうかを判別する関数を記述します。

Solution

LinkedListを走査するためのslowおよびfastポインターを利用します。 各反復で、slowポインターは1ステップ移動し、fastポインターは2ステップ移動します。

サイクルがない場合は、2つの結果が得られます。

1. LinkedListにサイクルがない場合、fastポインターはslowポインターの前にLinkedListの末尾に到達し、LinkedListにサイクルがないことを示します。
2. LinkedListにサイクルがない場合、slowポインターはfastポインターに追いつくことができません。

LinkedListにサイクルがある場合、fastポインターが最初にサイクルに入り、その後にslowポインターが続きます。この後、両方のポインタがサイクルを無限に動き続けます。 いずれかの段階でこれらのポインターの両方が出会った場合、LinkedListにサイクルがあると結論付けることができます。
2つのポインターが出会う可能性があるかどうかを分析しましょう。 fastポインターが背後からslowポインターに近づくと、2つの可能性があります。

1. fastポインターは、slowポインターの1つ後ろに位置します。
2. fastポインターは、slowポインターの2つ後ろに位置します。

fastポインターとslowポインターの間の他のすべての距離は、これら2つの可能性のいずれかに帰着します。
fastポインタが常に最初に動くことを考慮して、これらのシナリオを分析しましょう。

1. fastポインターがslowポインターの1つ後ろにある場合：fastポインターは2ステップ移動し、slowポインターは1ステップ移動し、両方が出会います。
2. fastポインターがslowポインターの2ステップ後ろにある場合：fastポインターは2ステップ移動し、slowポインターは1ステップ移動します。 移動後、fastポインタはslowポインタの1つ後ろになり、このシナリオは最初のシナリオに帰着します。

デモ

実装

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next

def has_cycle(head):
  # time complexity O(n)
  # space complexity O(1)
  fast, slow = head, head
  while fast is not None and slow is not None:
    fast = fast.next.next
    slow = slow.next
    if fast == slow:
      return True
  return False


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))


main()