(Leetcode) 141 - Linked List Cycle
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/linked-list-cycle/description/
Linked List 관련 문제이다.
최종 코드
from typing import Optional
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
visit = {}
current = head
hasCycle = False
while current is not None:
if id(current) not in visit:
visit[id(current)] = current
current = current.next
elif visit[id(current)].next is current.next:
hasCycle = True
break
return hasCycle
놓친 케이스
- [-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5]
- [1,1]
val 값이 unique 하다는 조건이 없었다. 이를 해결하고자 id 함수를 사용해서 ref id를 dict의 키 값으로 사용하도록 하였다.
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
모범답안
다른 사람의 답변을 참고해봤을 때 아래와 같은 풀이가 있었다. 2개의 포인터를 사용하여 next의 next까지 사용을 하여 해결하는 것을 볼 수 있었다.
cycle이 있다면 언젠가는 slow와 fast가 동일해지는 때가 있다는 것을 활용하였다. 쉽게 이해하자면 다음과 같은 비유를 들 수 있을 것 같다. 2명을 사람이 동일한 속도로 달리기를 하고 있을 때, 원형 코스라면 언젠가는 만나게 된다. 직선 코스라면 빨리 뛴 사람은 먼저 도착해서 쉬고 잇을 것이다.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
java 풀이 (24.05.01)
다시 풀 기회가 생겨서 이번에는 자바로 풀어보았다.
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
return true;
}
}
return false;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.