[LeetCode] 142 | Linked List Cycle II | Python

---

문제 링크: https://leetcode.com/problems/linked-list-cycle-ii/

---

문제

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.

---

조건

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

---

내 풀이

Floyd의 순환 찾기 알고리즘을 이용하면 된다.

 

우선, input list가 none이거나 길이가 1개인 경우는 cycle이 없다.

리스트 내에 사이클이 존재하지 않는다면 언젠가 None으로 끝나는 것이 존재한다.

리스트 내에 사이클이 존재한다면 리스트를 하나씩 건너갈 때(one = one.next)와 두개씩 건너갈 때(two = two.next.next) 언젠가 같은 노드위에 존재하게 된다. (1)

이렇게 사이클이 존재한다는 것을 알게되면, 어디서부터 시작하는지 확인해야 한다.

Floyd의 알고리즘을 사용하면, (1)이 끝났을 때의 위치에 one을 그대로 두고, 주어진 리스트의 처음위치에 또다른 노드를 두고(check), 한칸씩 전진했을 때 만나는 점이 순환이 시작하는 점이 된다.

---

코드

# 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]:
        if not head or not head.next:
            return
        
        one, two = head, head
        ans = False
        
        while two and two.next:
            one = one.next
            two = two.next.next
            
            if one == two:
                ans = True
                break
        
        if not ans:
            return
        
        check = head
        while check != one:
            check = check.next
            one = one.next
        return one