[Top Interview Questions] 141. Linked List Cycle

정답)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        
        tortoise, hare = head, head

        while tortoise and hare:
            if not hare.next:
                return False
                
            tortoise = tortoise.next
            hare = hare.next.next

            if tortoise == hare:
                return True

문제)

문제출처

 

head (주어진 linked list의 헤드 노드)가 주어졌을 때, head의 linked list에 사이클이 존재하는지 확인하시오.

 

노드의 next를 따라 계속 선형했을 때 linked list에 이미 존재했던 노드로 계속해서 이어진다면 사이클이 존재합니다.

사이클이 존재한다면 True, 존재하지 않는다면 False를 리턴하시오.

 

예시 1)

 

head = [3, 2, 0, -4]

output = True

 

예시 2)

 

head = [1, 2]

output = True

 

예시 3)

 

head = [1]

output = False

 

제한)

linked list의 노드 갯수는 0~10000개 입니다.

-100000 <= 노드의 val <= 100000

 

도전)

이 문제를 O(1)의 공간 복잡도로 풀 수 있습니까?

풀이)

이 문제는 dictionary를 이용한다면 너무나도 쉽게 풀 수 있겠지만 저흰 O(1)의 복잡도로 풀어볼 것입니다.

기본원리)

플로이드의 거북이와 토끼 알고리즘을 사용하여 풀어봅시다. 이 문제뿐만 아니라 다른 linked list와 사이클 관련된 문제는 이 알고리즘을 사용하는 듯했습니다.

 

거북이 노드는 1칸식, 토끼 노드는 2칸씩 움직이게 할 것입니다.

그렇게 움직이다 서로 만나게 되면 사이클이 존재하기 때문에 True를 리턴.

하지만 사이클이 존재하지 않아 토끼 노드가 Null을 만나게 되면 False를 리턴합니다.

 

def hasCycle(self, head: Optional[ListNode]) -> bool:        
        거북이, 토끼 노드들
        
        거북이와 토끼가 둘 다 Null이 아닐 때:
            만약 토끼 한 칸 뒤가 Null이면 False를 리턴
            
            거북이를 한 칸 옮김
            토끼를 두 칸 옮김
            
            거북이가 토끼와 같다면 True를 리턴

플로이드의 거북이와 토끼 알고리즘)

이 알고리즘은 linked list에 사이클이 존재한다면 거북이와 토끼는 무조건 만나게 되어있습니다.

 

간단한 예시와 그림으로 어떻게 작동되는지 봅시다.

 

거북이와 토끼 알고리즘

간단한 그림이지만 이 알고리즘이 어떻게 사용되는지는 이해하셨을 겁니다.

거북이가 한 칸, 토끼가 두 칸씩 움직이다 보면 사이클을 따라 언젠가는 만나게 된다는 것이죠.

초기세팅)

문제에서 head의 길이가 0일 수도 있다고 했기 때문에 만약 head가 Null이라면 바로 Flase를 리턴합니다.

 

그리고 head의 길이가 1보다 크거나 같다고 할 때 tortoise(거북이)와 hare(토끼)를 head에 지정해 줍니다.

일단 동일선상에서 시작하고 나중에 노드들을 옮겨줄 것입니다.

 

def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        
        tortoise, hare = head, head

노드들을 업데이트)

while문을 이용해 tortoise와 hare를 업데이트 및 비교를 해줄 건데 그러려면 두 노드들 다 Null이면 안 되겠죠?

 

그래서 두 노드 둘 다 Null이 아닐 때 hare의 next 노드를 확인해 줍니다.

hare 노드는 두 번 움직여야 되기 때문에 hare.next가 Null이면 안됩니다 (왜냐하면 Null.next를 실행할 수 없기 때문이죠)

 

그래서 만약 hare.next가 Null이라면 사이클이 존재하지 않는 것이기 때문에 False를 리턴합니다.

 

Null이 아니라면 tortoise를 한 칸, hare를 두 칸 움직여줍니다.

 

옮기고 난 후 두 노드들이 같다면 True를 리턴하면 되겠죠.

 

이 비교과정을 tortoise와 hare 둘 다 Null이 아닌 동안에 계속 돌려주면 정답이 나오겠습니다.

 

def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        
        tortoise, hare = head, head

        while tortoise and hare:
            if not hare.next:
                return False
                
            tortoise = tortoise.next
            hare = hare.next.next

            if tortoise == hare:
                return True

 

 

이번에도 새로운 컨셉이 나왔네요. 저같이 처음에 이런 걸 못 배운 사람들은 처음 릿코드 때 굉장히 답답한 거 같습니다. 내가 코딩을 못하나 자괴감도 들고요 ㅋㅋ. 그래도 다양한 개념을 배우는 것 같아서 머리가 차오르는 느낌입니다.

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)