leetcode/python/ 142. Linked List Cycle II

 

Description

Linked List Cycle II - LeetCode

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.

 

 

---

Process

Constraints:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

처음에 문제를 보고 일단 저장은 해야겠는데, 뭘 저장해야 할까를 조금 고민했다. node의 val을 저장할까? 그런데 val이 중복되지 않는다는 보장이 없었다. 그럼 이어지는 cycle을 리스트나 문자열 값으로 저장해놓고 같은 부분이 나오는지를 검증해볼까? 했는데 입력 값의 크기가 10^4이었다. 그런 짓은 하고 싶지 않았다.......

그러다가 아니 ListNode는 객체잖아? 라는 깨달음을 얻고 ListNode를 순회하면서 각 node를 set에 넣어두고 set에 node가 있다면 cycle이 존재하는 것으로 판단하도록 구현했다.

 

---

Solution: Time: 48 ms (83.68%), Space: 18 MB (8.44%)

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

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        duplicate = set()
        while head:
            if head in duplicate:
                return head
            duplicate.add(head)
            head = head.next
        return None

 

1. 중복 여부 (cycle 존재 여부)를 판단할 set을 선언한다.

2. head로부터 노드를 순회하면서 이미 방문한 적이 있던 노드라면 그 노드가 cycle의 시작점이 되는 것이므로 해당 노드를 반환한다.

3. 끝까지 반환 없이 순회한 경우 cycle이 없는 것이므로 None을 반환한다.

 

---

Conclusion

리트코드 몇 문제 풀어가면서 느끼는 건데 time이랑 space 판단 기준을 잘 모르겠다...... 처음에 같은 코드로 제출했을 때 Time: 57 ms (33.62%), Space: 17.9 MB (20.04%)가 나와서 음 더 효율적인 방법이 있나? 하고 다른 사람들 코드 보는데 투 포인터 썼길래 음 이게 더 빠른가 하고 돌려보고 다음에 다시 처음 제출한 코드로 돌려보니까 Time: 48 ms (83.68%), Space: 18 MB (8.44%)가 나온다. 테스트 케이스가 다를 것 같지는 않은데 실행 환경이 달라지는 건지 뭔지 잘 모르겠음. 그래서 앞으로는 연연하지 않기로 했다;