728x90
문제
주어진 LinkedList에 사이클이 존재하는지 여부를 판단할 것
Example 1
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
(이 때, 파라미터로는 시작 노드만 주어짐)
풀이1
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode node = head;
while (node != null && !set.contains(node)) {
set.add(node);
node = node.next;
}
return node != null;
}
참고
- HashSet 사용
- 노드를 통째로 Set에 add()
- 만약 똑같은 노드가 나온다면 중간에 멈출 것
- 이 때 현재 노드가 null이 아니라면 중간에 멈춘 것으로 판단
- 현재 노드가 null이라면 끝까지 순회한 것이니 true, 아니면 false 반환
- 시간복잡도 : O(N)
풀이2
public boolean hasCycle2(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return false;
}
return true;
}
참고
- 토끼와 거북이 알고리즘
- 거북이는 한 칸씩, 토끼는 두 칸씩 이동
- 순환구조가 있다면 토끼와 거북이가 언젠가 만나게 될 것이니 이를 통해 순환 여부를 판단
- 토끼는 두 칸씩 이동해야 하니 fast와 fast.next 둘 다 null이 아닐 경우에만 이동 가능
- slow와 fast가 일치할 경우 (똑같은 노드를 가리킬 경우) break
- 만약 fast가 null이거나 fast.next가 null일 경우 (토끼가 리스트에 끝에 도달할 경우 = 순환X) false 반환, 아니라면 true 반환
- 시간복잡도 : O(N)
💬 공간복잡도 면에서 효율적인 풀이
'JAVA > Coding Test Study' 카테고리의 다른 글
[Easy] LeetCode - no.104 Maximum Depth of Binary Tree : Java (0) | 2024.10.23 |
---|---|
[Easy] LeetCode - no.21 Merge Two Sorted Lists : Java (0) | 2024.10.21 |
[Easy] LeetCode - no.20 Valid Parentheses : Java (0) | 2024.10.19 |
[Easy] LeetCode - no.228 Summary Ranges : Java (0) | 2024.10.19 |
[Easy] LeetCode - no.219 Contains Duplicate II : Java (0) | 2024.10.17 |