[python3] 142. Linked List Cycle II

풀이 일자: 23.03.09

난이도: [Medium]

분류: [Hash Table, Two Pointer]

문제 내용

LinkedList의 head가 주어졌을 때 cycle이 시작되는 노드를 리턴하고 cycle이 없으면 null을 리턴하는 문제이다.

Follow-up으로 자료구조 이용하지 않고 풀기.

 

 

문제 해결 흐름

1. 우선 포인터를 하나만 사용한다면 cycle이 없는지는 확인이 가능한데 그거 외에는 가능한게 없다.

→ Two-pointer를 사용해야겠다.

 

2. Two-pointer을 사용하는데 cycle이 있음을 확인하려면 두 개의 포인터의 이동 속도가 달라야겠다.

→ 포인터 하나는 한 칸씩 움직이고 나머지 하나는 두 칸씩 움직인다.

 

3. 이거랑 관련된 알고리즘이 있다.

→ 플로이드-마샬 알고리즘으로 유명한 플로이드의 Floyd's cycle-finding algorithm

 

# 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]:
        turtle = rabbit = head;
        i = 0; loop = -1;
        while(rabbit and rabbit.next):
            turtle = turtle.next;
            rabbit = rabbit.next.next;
            if turtle == rabbit:
                turtle = head;
                while(turtle != rabbit):
                    turtle = turtle.next;
                    rabbit = rabbit.next;
                return turtle

        return None;

 

Time Complexity: O(NM)

LinkedList를 탐색하고 내부에서도 초기 노드를 찾기 위해 While문을 돌리기에 NM정도의 시간복잡도를 가질 것이다.

 

Space Complexity: O(1)

일반적인 변수를 제외하고 어떤 자료구조를 문제풀이에 사용하지 않았기 때문에 1의 공간복잡도를 가지게 될 것이다.

 

 

다른 해결 방식

이 문제를 해결하기 위한 알고리즘이기 때문에 대부분 플로이드 사이클 탐색 알고리즘을 사용해 풀었다.

 

 

문제 링크

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

Linked List Cycle II - LeetCode