리트코드 141. Linked List Cycle JAVA

문제

문제 해석

이건 링크드 리스트가 순환 링크드 리스트인지 여부를 물어보는 문제다.
즉 토끼와 거북이 알고리즘을 이용하면 쉽게 문제를 풀 수 있다.

여담이지만 Discussion 탭에 여러분이 토끼와 거북이 알고리즘을 몰라서 못푸는 거지 실력이 없는게 아닙니다 라고 쓴 글이 조금 재밌었다.

토끼와 거북이 알고리즘이란 (Floyd's Tortoise & Hare Algorithm)

Floyd's Tortoise & Hare Algorithm
프로이드가 만든 알고리즘으로 순환을 확인하기 위해 사용한다.

칸수로 설명을 하자면 하나의 변수는 2칸씩 증가하고 하나의 변수는 1칸씩 증가한다.
이 때 2칸씩 증가하는 변수가 null 이 되면 순환하지 않는 것이다.
그게 아니라면 언젠가는 1칸씩 이동하는 변수와 2칸씩 이동하는 변수가 같은 값을 나타낸다라는 것을 의미한다

리트코드에서 발췌

한칸씩 이동하는 코드는 2칸씩 이동하는 코드와 언젠간 만난다.

* 9 에서 시작했다고 가정해보자.

int a = 9

int b = 9

시행 횟수	int a	int b
1	5	1
2	6	5
3	7	3
4	1	6
5	3	8
6	8	7
7	9	9

7번째에서 서로 같아지게 된다.

수도 코드

    r = head
    t = head

    while(r != null && r.next != null && r.next.next != null){
        r = r.next.next;
        t = t.next;

        if(서로 같으면)
            true
    }
    false

코드를 보면 간단하다

코드

/**
 * 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) {
        ListNode rabbit = head;
        ListNode turttle = head;
        while(rabbit != null && rabbit.next != null && rabbit.next.next != null){
            rabbit = rabbit.next.next;
            turttle = turttle.next;
            if(rabbit == turttle)
                return true;
        }
        return false;
    }
}

다른 사람 코드

public class Solution {
    public boolean hasCycle(ListNode head) {

        ListNode s = head;
        ListNode f = head;
        while(f!=null && f.next!=null){
            s = s.next;
            f = f.next.next;
            if(s==f){
                return true;
            }
        }
        return false;

    }
}

코드를 보면 검증할 때 나보다 1개를 덜 검증한다.

반복을 하나 더하는 대신 동작을 1개 줄이게 된다.

회고

로직을 알고 있으면 생각보다 쉽게 풀 수 있다.