Linked List Cycle

문제

주어진 head는 연결 리스트의 헤드(시작 노드)입니다. 연결 리스트에 사이클이 있는지 확인하세요. 연결 리스트에 사이클이 있다면, 다음 포인터를 계속 따라갈 때 어떤 노드를 다시 만날 수 있는 경우를 말합니다. 내부적으로, pos는 꼬리의 다음 포인터가 연결된 노드의 인덱스를 나타내는 데 사용됩니다. 주의하실 점은 pos는 파라미터로 전달되지 않습니다. 연결 리스트에 사이클이 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

최초 풀이

두 개의 포인터를 사용하여 하나의 포인터는 두 칸씩 이동하고 다른 하나의 포인터는 한 칸씩 이동하게 한 뒤 두 칸씩 이동하는 포인터가 추월하거나 그 전에 한 칸씩 이동하는 포인터와 만나게 될 경우 연결 노드는 원형으로 이어져 있는 구조임을 알 수 있다. 하지만 아래 코드에서 계속해서 while 문을 반복하기 때문에 노드가 끊어진 구조에서는 탈출할 수 없어 시간초과가 발생하였다.

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        follow = head
        while head:
            lead = head.next.next
            follow = follow.next
            if lead == follow:
                return True
        return False

수정

class Solution(object):
  def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        lead = head
        while lead is not None and lead.next is not None:
          head = head.next
          lead = lead.next.next
          if head is lead:
            return True
        return False

# _: slow pointer, 1칸씩 이동
# -: fast pointer, 2칸씩 이동

1 -> 2 -> 3 -> 4 -> 5 -> 1 ...
_         -

1 -> 2 -> 3 -> 4 -> 5 -> 1 ...
     _              -

1 -> 2 -> 3 -> 4 -> 5 -> 1 ...
     -    _

# 두 포인터가 만나고 True 반환
1 -> 2 -> 3 -> 4 -> 5 -> 1 ...
               -_