•
•
문제 설명 : 제공된 연결리스트가 순환되는 구조인지 반환
•
풀이 방법
◦
이전에 확인한 노드를 해시테이블에 저장하여 확인하는 방식을 사용하였다.
•
시간복잡도 :
•
성공 코드
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
node_info = set()
cursor = head
while cursor != None:
if cursor in node_info:
return True
node_info.add(cursor)
cursor = cursor.next
return False
Python
복사
•
성공 코드
Solution을 확인하니, 공간 복잡도도 같이 줄일 수 있는 방법이 있었다.
바로 “토끼와 거북이” 알고리즘으로, 보통 투포인터에서 많이 사용하는 방법이다.
만약 순환되는 구조가 아니라면, 두 커서는 절대 만날 수 없다는 방법을 이용한 것이다.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast = head
# fast가 None이 아니라면 계속 진행
while fast and fast.next:
head = head.next
fast = fast.next.next
# 만약 두 커서가 만난다면 순환구조
if head is fast:
return True
# None으로 끝난다면 순환구조가 아니다.
return False
YAML
복사