참고
문제해설
NOTE
•
입력값 ⇒ 연결 리스트 배열과, 순환으로 이동하는 pos 정수
•
출력값 ⇒ 주어진 연결리스트는 순환되는가?
•
순환 ⇒ 포인터를 계속 따라가다가 다시 도달할 수 있는 지점이 있다.
문제 로직고민
NOTE
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
}
}
Java
복사
문제가 다음과 같이 주어졌다.
•
ListNode의 next가 null이 나올때까지 계속해서 순회한다.
◦
여기서 만약 방문한 ListNode를 만난다면 순환한다는 의미이므로 순회를 멈춘다.
◦
null이 나온다면 순환이 없다는 의미이다.
•
어떻게 동일한 Node임을 파악하는가?
◦
문제에 각 Node의 val이 유일한다는 조건이 없어 고민하게된 문제이다.
◦
중복처리를 Map으로 진행할것이므로 equals를 통해 동일노드인지 판단한다.
작성코드
NOTE
public class Solution {
public boolean hasCycle(ListNode head) {
HashMap<ListNode, Integer> map = new HashMap();
while(head != null){
// 동일 노드가 없다.
if(!map.containsKey(head)) map.put(head, 1);
// 동일 노드가 있다 (순환있음)
else return true;
head = head.next;
}
return false;
}
}
Java
복사
정답코드
NOTE
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next !=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
플로이드의 사이클 검출 알고리즘(Floyd's Cycle Detection Algorithm)을 사용한 코드이다.
•
강의자료에 있어 기억은 하고 있었는데 성능적으로 정말로 좋은가 긴가민가 했는데 실제로 보니 체감이 되는것 같다.
◦
순환이 없다 ⇒ fast pointer는 2개씩 건너뛰므로, 순환이 없는경우 빠르게 찾는다.
◦
순환이 있다 ⇒ 결국 slow pointer와 fast pointer는 아무리 늦어도 n번째에서 만난다.
•
그런데 개선방안에 O(1)의 방식으로 풀 수 있는가를 고려해보라는데 이는 도대체 어떤 방식으로 푸는지 감이 잡히지 않는다.
◦
LinkedList에서 순환을 O(1)의 방식으로 찾을 수 있는가?
◦
Double LinkedList라면 역탐색으로 가능할것 같지만, Single Linked List에서 이게 가능한지는 잘 모르겠다.