[토끼와 거북이 알고리즘 + 테스트 코드] Leetcode 141. Linked List Cycle
Linked List Cycle - LeetCode
Can you solve this real interview question? 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 continuo
leetcode.com
https://github.com/fineman999/algorithm_java/issues/4
141. Linked List Cycle · Issue #4 · fineman999/algorithm_java
링크
github.com
1. 서론
알고리즘 문제 내용으로 해당 Linked List가 cycle인지를 확인하는 판별하는 문제이다.
해당 문제를 풀기 위해선 토끼와 거북이 알고리즘을 알아야 된다. 사이클 판별 뿐만 아니라 사이클 시작 위치, 사이클 길이를 알 수 있다.
테스트 코드를 작성해보면서 토끼와 거북이 알고리즘를 구현해보자.
2. 알고리즘
head를 가진 Linked List가 주어진다. cycle를 가지는지 판별하자.
포인터들을 따라가다가 다시 도달할 수 있는 노드가 있으면 cycle를 가지므로 true를 반환하게 된다.
pos는 마지막 노드인 tail이 다음 노드를 가르키는 인덱스를 나타내는 데 사용된다. pos는 매개변수로 전달 되지 않는다.
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).
3. ListNode
/**
* 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) {
return false;
}
}Leetcode에서 제공해주는 클래스이다.
위의 코드를 토대로 알고리즘을 구현하기 위한 최소한의 코드를 만들어보자.
3.1 테스트 코드 작성
class ListNodeTest {
@Test
@DisplayName("of 메서드는 int[] 를 받아 ListNode 를 생성한다.")
void of() {
int[] values = {1, 2, 3, 4, 5};
ListNode curr = ListNode.of(values);
for (int value : values) {
assertThat(value).isEqualTo(curr.val);
curr = curr.next;
}
}
@Test
@DisplayName("of 메서드는 int[] 가 null 일 때 IllegalArgumentException 을 던진다.")
void ofException() {
int[] values = null;
assertThatThrownBy(() -> ListNode.of(values))
.isInstanceOf(IllegalArgumentException.class);
}
@Test
@DisplayName("setPos 메서드는 ListNode head 와 int pos 를 받아 마지막 노드의 next 를 pos 번째 노드로 설정한다.")
void setPost() {
int pos = 1;
int lastNodeValue = 4;
ListNode head = ListNode.of(3, 2, 0, -4);
ListNode.setPos(head, pos);
ListNode posNode = head;
for (int i = 0; i < pos; i++) {
posNode = posNode.next;
}
ListNode lastNode = head;
for (int i = 0; i < lastNodeValue; i++) {
lastNode = lastNode.next;
}
assertThat(posNode).isEqualTo(lastNode);
}
@Test
@DisplayName("setPos 메서드는 ListNode head 와 int pos 가 -1 일 때 cycle을 만들지 않는다.")
void setPostNot() {
int pos = -1;
ListNode head = ListNode.of(3, 2, 0, -4);
ListNode.setPos(head, pos);
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
assertThat(curr.next).isNull();
}
}
컴파일 에러를 제외한 클래스를 만들고 테스트를 실행했다.
boolean hasCycle(ListNode head)를 만들기 위한 최소한의 기능이 필요하다고 판단했다.
- static ListNode of (int... values): 여러개의 int 값을 받아 Linked list를 생성하게 된다.
- static void setPos(ListNode head, int pos): pos가 index가 유효하면 마지막 노드와 해당 index의 노드와 연결이 된다.
3.2 프로덕션 코드 작성
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
public static ListNode of(int... values) {
if (values == null) {
throw new IllegalArgumentException("values cannot be null");
}
ListNode head = new ListNode(values[0]);
ListNode curr = head;
for (int i = 1; i < values.length; i++) {
curr.next = new ListNode(values[i]);
curr = curr.next;
}
return head;
}
public static void setPos(ListNode head, int pos) {
if (pos == -1) {
return;
}
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
ListNode posNode = head;
for (int i = 0; i < pos; i++) {
posNode = posNode.next;
}
curr.next = posNode;
}
}
4. 토끼와 거북이 알고리즘
4.1 알고리즘 풀이 - 사이클인지 확인
이전에 공부했던 토끼와 거북이 알고리즘이 떠올랐다.
https://github.com/fineman999/Algorithm/issues/105
이론: 토끼와 거북이 알고리즘(Tortoise and hare Algorithm) · Issue #105 · fineman999/Algorithm
유튜브 출저: 주니온TV 아무거나 연구소 문제 1 ( 사이클인지 확인) 주어진 연결 리스트가 사이클이 있는 리스트인지 판단하라. 입력: 연결 리스트의 head 출력: 사이클이 있으면 true, 없으면 false를
github.com
의사코드 - 사이클 판별
- 토끼와 거북이는 같은 장소에서 출발한다.
- 토끼와 거북이가 서로 만나지 않으면 다음을 반복한다.
- 만약 토끼와 거북이 중 하나라도 null 경우
- false를 반환한다.
- 토끼는 두 칸을 전진한다.
- 거북이는 한 칸을 전진한다.
- 토끼와 거북이가 같은 노드에 위치했으면
- true를 반환함과 동시에 반복문을 빠져나온다.
- 만약 토끼와 거북이 중 하나라도 null 경우
- 위의 조건에 만족하지 않고 반복문을 빠져나올 경우 false를 반환한다
그림 - 사이클 판별
결과로 총 3번 반복하고 값이 -4인 노드에서 만나게 된다.
4.2 테스트 코드 작성
class SolutionTest {
private final Solution solution = new Solution();
@Test
@DisplayName("hasCycle 메서드는 ListNode인 head [3, 2, 0, -4]를 받고 pos가 1이면 true 를 반환한다.")
void hasCycle() {
ListNode head = ListNode.of(3, 2, 0, -4);
ListNode.setPos(head, 1);
boolean actual = solution.hasCycle(head);
assertThat(actual).isTrue();
}
@Test
@DisplayName("hasCycle 메서드는 ListNode인 head [1, 2]를 받아 pos가 0이면 true 를 반환한다.")
void hasCycle2() {
ListNode head = ListNode.of(1, 2);
ListNode.setPos(head, 0);
boolean actual = solution.hasCycle(head);
assertThat(actual).isTrue();
}
@Test
@DisplayName("hasCycle 메서드는 ListNode인 head [1]를 받아 pos가 -1이면 false 를 반환한다.")
void hasCycle3() {
ListNode head = ListNode.of(1);
ListNode.setPos(head, -1);
boolean actual = solution.hasCycle(head);
assertThat(actual).isFalse();
}
}
문제 예제에 따라 hasCycle을 통해 true, false를 반환하는 테스트 코드를 작성하였다.
4.3 프로덕션 코드 작성
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode tortoise = head;
ListNode hare = head;
while (hare != null) {
if (hare.next == null) {
return false;
}
tortoise = tortoise.next;
hare = hare.next.next;
if (tortoise == hare) {
return true;
}
}
return false;
}
}
위와 같이 테스트를 통과한 걸 알 수 있다.
5. 사이클의 시작위치를 알고싶으면?
사이클 판별 여부를 통과함으로써 이전 코드와 그림에서 증명되었다.
이전에는 만났을 때 종료하는 메소드를 구현이 끝이었다.
하지만 사이클의 시작위치를 알고 싶으면 추가적인 로직이 필요하다.
의사코드 - 사이클 시작 위치
- 토끼와 거북이는 같은 장소에서 출발한다.
- 토끼와 거북이가 서로 만나지 않으면 다음을 반복한다.
- 만약 토끼와 거북이 중 하나라도 null 경우
- null를 반환한다.
- 토끼는 두 칸을 전진한다.
- 거북이는 한 칸을 전진한다.
- 토끼와 거북이가 같은 노드에 위치했으면
- 토끼를 다시 시작위치로 옮긴다.
- 토끼와 거북이가 한 칸씩 움직인다.
- 만나는 지점이 시작위치이므로 node로 반환한다.
- 만약 토끼와 거북이 중 하나라도 null 경우
- 위의 조건에 만족하지 않고 반복문을 빠져나올 경우 null를 반환한다.
그림 - 사이클 시작 위치
5.1 코드
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode tortoise = head;
ListNode hare = head;
while (hare != null) {
if (hare.next == null) {
return null;
}
tortoise = tortoise.next;
hare = hare.next.next;
if (tortoise == hare) {
return getNode(head, tortoise); // 추가
}
}
return null;
}
private ListNode getNode(ListNode head, ListNode tortoise) {
ListNode hare;
hare = head;
while (tortoise != hare) {
tortoise = tortoise.next;
hare = hare.next;
}
return hare;
}getNode 함수도 새로 생기고 나머지 로직은 비슷하다.
6. 사이클의 길이를 알고싶으면?
시작 노드를 위치를 알았으니 길이를 구하는 것은 어렵지 않다.
시작 노드를 저장하고 반복문 후 다시 시작 노드를 찾으면 그때의 길이를 알 수 있다.
public int getCycleLength(ListNode head) {
ListNode start = detectCycle(head); // 이전에 구현한 detectCycle 메서드를 사용한다.
if (start == null) {
return 0;
}
ListNode curr = start;
int length = 0;
while (curr != null) {
curr = curr.next;
length++;
if (start == curr) {
return length;
}
}
return length;
}전체 테스트 결과
