[leetcode] 141. Linked List Cycle

 

https://leetcode.com/problems/linked-list-cycle

 

 

이 문제를 해결할 두 가지 아이디어를 설명한다.

 

첫번째는, Set 을 사용하는 것이다.

주어진 Linked List 를 순회하면서 만나는 Node 를 Set 에 모두 담는다.

이미 Set 에 담긴 Node 를 만나면 True 를 반환하고, 그렇지 않으면 False 를 반환한다.

Node 개체가 갖는 고유의 id 를 담은 Set 을 통해 중복 여부를 확인할 수 있다.

 

두번째는, 두 개의 pointer 를 사용하는 것이다.

첫번째 포인터는 Linked List 를 한 번에 한 개씩 순회한다.

두번째 포인터는 Linked List 를 한 번에 두 개씩 순회한다.

만약 Cycle 이 존재한다면, 무조건 첫번째 포인터보다 2배 앞서나가는 두번째 포인터가 첫번째 포인터와 만나게된다.

두번째 포인터가 None 을 만난다면 Cycle이 존재하지 않는다는 의미이므로 False 를 반환한다.

while 문에서 첫번째 포인터가 None 인지 검사 할 필요는 없다.

왜냐하면 첫번째 포인터는 이미 두번째 포인터가 지나온 길을 따라가기 때문이다.

 

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if(not head or not head.next): return False
        ahead = head.next
        while(ahead):
            if(head == ahead): return True
            head = head.next
            ahead = ahead.next
            if(not ahead): return False
            ahead = ahead.next
        return False

 

---

 

 

 

< English (feedback by ChatGPT) >

 

I will explain the two ideas for this problem.

(I'll explain two ideas to solve this problem.)

 

First is to use a set.

(First, we can use a set.)

 

We iterate through the given linked list and insert all nodes we encounter during the traversal into a set .

(We iterate through the given linked list and add every node we encounter to a set.)

 

If we encounter a node which exists in the set, return True, or return False.

(If we encounter a node that already exists in the set, we return True; otherwise, we return False.)

 

A node object has its unique id so we can check duplication using the id in a set.

(Since each node object has a unique identity (id), we can use this to detect duplicates.)

 

Second is to use two pointers.

(Second, we can use two pointers.

 

A first pointer iterates the given linked list with one step at a time.

(The first pointer traverses the linked list one step at a time.)

 

A second pointer iterates the given linked list with two steps at a time.

(The second pointer moves two steps at a time.)

 

If a cycle exists, the second pointer must meet the first pointer because the second pointer goes ahead of the first pointer double times.

(If a cycle exists, the second pointer will eventually meet the first pointer because it's moving twice as fast.)

 

If the second pointer encounters None, return False because it means a cycle doesn't exist.

(If the second pointer encounters None, it means there's no cycle, so we return False.)

 

We don't need to check whether the first pointer is None at while statement

(We don't need to check whether the first pointer is None in the while loop,)

 

Because the first pointer tracks the path which the second pointer passed before.

(because it always follows the path already taken by the second pointer.)