[Grind75-Leetcode] Linked List Cycle - Easy
접근
- 플로이드의 토끼와 거북이(Floyd's Tortoise and Hare)
풀이
노드가 연결된 리스트에 사이클이 존재하는지 알아내는 문제이다. 해당 사이트의 다른 문제들과 같이 배열이나 리스트 형태의 값이 주어지는 게 아닌 노드가 다음 노드의 값을 들고 있는 형태로 루트 노드 하나가 입력으로 주어진다. 편법으로 문제를 열심히 풀어왔던 나로서는 현재 노드의 값과 다음 노드의 값을 set에 저장한 뒤 똑같은 값이 나오면 한 바퀴를 돌았다는 말이니 true를 반환하면 되지 않을까? 하는 생각으로 풀어봤다. 그러나 노드 객체가 달라도 값이 같은 경우가 있고 예시 설명을 볼 땐 배열에 값이 들어있는 구조로 보여주기 때문에 통과하지 못한 방법이었다. 결론은 연결된 노드 객체 자체가 같아야 사이클이 형성되어 있다고 볼 수 있는 문제이다.
플로이드의 토끼와 거북이라는 알고리즘이 있다. 전래동화인 토끼와 거북이에서 이름을 딴 알고리즘으로 빠르게 달릴 수 있는 토끼와 느린 거북이를 사용해 푸는 방법이다. 거북이는 느리기 때문에 한 번에 한 칸씩 움직인다. 토끼는 빠르기 때문에 한 번에 두 칸씩 움직인다. 그렇게 계속 움직이다 보면 토끼가 결승선에 들어가게 되는 경우와 한 바퀴를 돌아 다시 거북이를 만나게 되는 경우가 생긴다. 결승선에 들어가는 경우 다음 노드가 null로 존재하지 않아 사이클이 없는 경우이고 다시 거북이를 만나게 되는 경우는 사이클이 존재해 앞질렀던 거북이를 다시 만나게 되는 경우이다.
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}코드를 통해 구현된 모습이다. slow 객체는 거북이, fast 객체는 토끼를 나타낸다. while 문 아래에서 거북이는 다음 객체인 next로 토끼는 next의 다음 객체인 next.next로 이동하게 되고 사이클을 통해 토끼가 다시 거북이를 만나거나 사이클이 없는 경우 노드의 끝 까지 반복을 수행한다.
전체 코드
/**
* 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) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}