[Leetcode] #141 Linked List Cycle 링크드 리스트에 끝이 있는지 확인하기

문제 요약

자세한 내용은 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;
}