141. Linked List Cycle

주어진 linked list가 순환하는지 판별하는 문제이다. 

이전에 234번에서 풀었던 Runner 기법을 이용하면 쉽게 풀린다.

hongprogrammer.tistory.com/entry/234-Palindrome-Linked-List

234. Palindrome Linked List

slow는 한칸씩 가면서, fast는 두칸씩 전진해서 나간다. 

무한 반복해가면서 같은것이 나올때까지 돌린다.

    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            print(slow.val, fast.val)
            slow, fast = slow.next, fast.next.next
            if slow == fast: return True
        return False

 

 

 

while문이 어떻게 종료되는지에 대해서 부가 설명을 해보자면, 

linked list ex)  3->2->0->-4 

-4이후에 다시 2로 연결되는 구조라면 while문에서 slow, fast가 돌면서 언제가는 만나게 되어있다. 

 

만약 순환구조가 아니라면 fast.next에 None이 들어와서 끊기게 되므로 저절로 종료가 되는 구조이다.