문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/linked-list-cycle/
링크드 리스트가 순환하는지 확인해라. 다른 말로는 링크드 리스트의 마지막 노드가 null을 다음 노드로 가지고 있는지 확인해라.
예제
풀이
2 포인터 문제로 풀 수 있다.
slow 포인터는 한 번에 한 노드씩, fast 포인터는 한 번에 두 노드씩 움직이면서 두 포인터가 서로 만날 경우 fast 포인터는 이미 리스트를 한바퀴 이상 돌았기 때문에 cycle임을 알 수 있다.
fast 포인터의 현재 노드나 현재의 다음 노드가 null일때까지 loop을 계속 수행한다.
public boolean hasCycle(ListNode head) {
// 베이스 케이스. head가 null이면 바로 반환한다.
if (head == null) return false;
ListNode curr = head;
ListNode slow = curr;
ListNode fast = curr.next;
while (fast != null && fast.next != null) {
// 만약 두 개의 포인터가 서로 만났다면 그거슨 cycle!
if (slow == fast) return true;
// 한 번에 하나의 노드씩 움직인다
slow = slow.next;
// 한 번에 두개의 노드씩 움직인다
fast = fast.next.next;
}
// 여기까지 왔다면 fast 포인터가 null을 만났다는 의미이므로 false를 반환한다
return false;
}