2021-02-03] Linked List Cycle

오늘의 문제: leetcode.com/explore/featured/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3627/

Explore - LeetCode

제목에서처럼 Linked List안에 Cycle이 있으면 True, 없으면 False 값을 반환하는 쉬운 문제이다.

 

해당 문제의 경우 cycle을 파악하는 것에 대해 아는 것이 핵심인데,

 

이럴 때, 사용하는 방법은 pointer 2개를 이용하는 것이다.

 

예를 들어 첫 head에서 시작하는 pointer 2개가 움직이는 범위를 달리하여, 움직이면 처음만 같고,

 

Cycle이 없는 이상 두 pointer 끝까지 만날 수 없다. 이를 이용한 방법이라고 할 수 있다.

 

아래 코드를 보며 이해해보면 좋을 것 같다.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fp=head # head 값을 가지는 fast pointer, slow pointer 2개 선언
        sp=head
        while sp and fp and fp.next: # 하나의 pointer가 None을 만나면 cycle이 없다.
            sp=sp.next
            fp=fp.next.next # pointer가 옮겨지는 차이를 둔다.
            
            if sp is fp: # pointer 두개가 만나게 된다면 cycle이 있다.
                return True
        return False