이론: 토끼와 거북이 알고리즘(Tortoise and hare Algorithm)

[fineman999]

유튜브 출저: 주니온TV 아무거나 연구소

문제 1 ( 사이클인지 확인)

• 주어진 연결 리스트가 사이클이 있는 리스트인지 판단하라.
  • 입력: 연결 리스트의 head
  • 출력: 사이클이 있으면 true, 없으면 false를 리턴

# Dfinition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def hasCycle(self, head: ListNode) -> ListNode:
        hare = tortoise = head
        while hare != None and tortoise != None:
            if hare.next == None:
                return False
            hare = hare.next.next
            tortoise = tortoise.next
            if hare == tortoise:
                return True
            return False

추가 문제

• 시간 복잡도가 O(1)으로 풀 수 있는가?

Floyd's tortoise and hare algorithm

• 서로 다른 속도로 움직이는 두 개의 포인터를 이용해서 O(n), O(1) 공간 복잡도로 Cycle Detection Problem을 해결하는 알고리즘

1. 토끼와 거북이는 같은 장소에서 출발한다.
2. 토끼와 거북이가 종점 노드를 만나지 않으면 다음을 반복한다.
   1. 토끼는 두 칸을 전진한다.
   • 중간에 종점 노드를 만나면 사이클이 없다고 리턴한다.
   2. 거북이는 한 칸을 전진한다.
3. 만약 연결 리스트 내에 사이클이 없다면 토끼와 거북이는 이동 중에 NULL 노드를 만날 것이다.
4. 만약 연결 리스트 내에 사이클이 있다면 토끼와 거북이가 언젠가 반드시 만나게 될 것이다.

문제 2 (사이클의 시작위치)

• 주어진 연결 리스트가 사이클의 시작 노드를 찾아라.
  • 입력: 연결 리스트의 head
  • 출력: 사이클이 있으면 시작노드, 없으면 null을 리턴

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        hare = tortoise = head
        while hare != None and tortoise != None:
            if hare.next == None:
                return None
            hare = hare.next.next
            tortoise == tortoise.next
            if hare == tortoiseL
                # Phase 2: Finding the starting position
                hare = head
                while hare != tortoise:
                    hare = hare.next
                    tortoise = tortoise.next
                return hare
        return None

추가 문제

• 시간 복잡도가 O(1)으로 풀 수 있는가?

1. 토끼와 거북이는 같은 장소에서 출발한다.
2. 토끼와 거북이가 종점 노드를 만나지 않으면 다음을 반복한다.
   1. 토끼는 두 칸을 전진한다.
   • 중간에 종점 노드를 만나면 사이클이 없다고 리턴한다.
   2. 거북이는 한 칸을 전진한다.
   3. 토끼와 거북이가 같은 노드에 위치했으면
      1. 토끼를 처음 위치로 보낸다.
      2. 토끼와 거북이가 만날 때까지 둘 다 한 칸 씩 이동한다.
      3. 토끼와 거북이가 만난 위치의 노드(사이클 시작 노드)를 리턴한다.
3. 토끼와 거북이가 같은 노드를 만났으므로 null를 리턴한다.

문제3 (사이클의 길이)

1. 토끼와 거북이는 같은 장소에서 출발한다.
2. 토끼와 거북이가 종점 노드를 만나지 않으면 다음을 반복한다.
   1. 토끼는 두 칸을 전진한다.
   • 중간에 종점 노드를 만나면 사이클이 없다고 리턴한다.
   2. 거북이는 한 칸을 전진한다.
   3. 토끼와 거북이가 같은 노드에 위치했으면
      1. 토끼를 처음 위치로 보낸다.
      2. 토끼와 거북이가 만날 때까지 둘 다 한 칸 씩 이동한다.
      3. 토끼와 거북이가 만난 위치의 노드(사이클 시작 노드)를 리턴한다.
3. 토끼와 거북이가 같은 노드를 만났을때 이때부터 같이 사이클을 돈다.
4. 다시 시작 노드에 위치가 되면 그 길이만큼 리턴한다.

[fineman999]

텀 프로젝트