문제
링크된 목록의 선두인 헤드가 지정되면 링크된 목록에 사이클이 있는지 확인합니다.
목록에 다음 포인터를 계속 따라가면 다시 도달할 수 있는 노드가 있는 경우 링크된 목록에 사이클이 있습니다. 내부적으로 pos는 테일의 다음 포인터가 연결되는 노드의 인덱스를 나타내기 위해 사용됩니다. pos는 파라미터로 전달되지 않습니다.
링크 목록에 주기가 있는 경우 true를 반환합니다. 그렇지 않으면 false를 반환합니다.
https://leetcode.com/problems/linked-list-cycle/
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
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).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
풀이
자바입니다.
- LinkedList 의 각 노드는 다른 객체입니다.
Two Pointers
- 빠른 포인터와 느린 포인터를 만듭니다.
- 주기가 없는 경우 빠른 포인터는 연결된 목록의 끝에서 중지됩니다.
사이클이 있는 경우 고속 포인터는 저속 포인터와 만나게 됩니다.
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) return true;
}
return false;
}
}HashSet
- HashSet의 값의 중복이 안 된다는 특성을 이용합니다.
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
ListNode node = head;
while(node!=null){
if(set.contains(node)) return true;
set.add(node);
node = node.next;
}
return false;
}
}LinkeList의 각 Node가 다른 객체라는 것을 생각하지 못하고 단순 Node.val 값만 비교하려 했습니다. 각 Node는 다른 객체입니다.
