•
문제 설명 : 주어진 연결리스트가 순환되는 경우, 순환이 시작되는 노드를 반환한다.
•
풀이 방법
◦
플로이드의 토끼와 거북이 알고리즘을 사용할 수 있다.
▪
아래 문제와도 거의 동일하다. 단 이번 문제는 사이클 여부인지만 확인하지 않고 어떤 노드에서 시작되는지까지 확인해야한다.
•
시간복잡도 :
•
성공 코드
다만, 처음 사용한 방법은 해시 테이블을 사용한 방법이었다.
이 방법은 O(N) 만큼의 공간 복잡도가 필요한 단점이 있다.
# 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]:
node_info = set()
cursor = head
index = 0
while cursor:
if cursor.next == None:
return
if cursor in node_info:
return cursor
node_info.add(cursor)
cursor = cursor.next
index += 1
Python
복사
아래 코드는 위에서 언급한 플로이드의 알고리즘을 사용하는 방식이다.
투 포인터의 방식을 사용하며, 공간 복잡도는 O(1)이다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow, fast = slow.next, fast.next
return slow
Python
복사