LeetCode 141 Linked List Cycle

nayu1105·2023년 8월 28일

leetcode 알고리즘

LeetCode

목록 보기

13/28

LeetCode 141 Linked List Cycle 풀러가기

문제

주어지는 ListNode에 사이틀 유무를 판단하는 함수를 짜는 문제였다.

ListNode는 자신의 숫자 value와 다음 노드 next를 가지고 있다.

문제 분석

첫번째 시도

같은 노드를 다시 방문하지 않으면 되니까 set을 사용하여 풀었다.

set을 Integer로 할당하여, 같은 value를 가지면 (contains 함수 사용) true를 리턴하도록 짰다.

value가 없다면 set에 추가하고, 계속 다음 노드를 탐색하도록 했다.

만약 다음 노드가 null이라면 사이클이 아닌 것으로 fasle를 리턴했다.

이 알고리즘은 최대 ListNode의 길이 만큼 탐색하기 때문에 O(N)이 걸렸다.

코드

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

 import java.util.HashSet;

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<Integer> visited = new HashSet<>();
        if(head==null)return false;
        while(!visited.contains(head.val)){
            visited.add(head.val);
            head = head.next;
            if(head==null)return false;
        }
        return true;
    }
}

결과 : 실패

이유

ListNode의 value 값으로 이미 방문한 노드인지 확인했는데, value 다른 노드끼리도 같을 수 있어서 틀렸다.

문제 이해를 잘못한 것이였다.

두번째 시도

value값으로 노드를 분류할 수 없으니, set을 ListNode 객체를 기준을 만들었다.

그리고 노드 자체가 있는지 확인하는 코드를 짰다.

코드

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

import java.util.HashSet;

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();
        if(head==null)return false;
        while(!visited.contains(head)){
            visited.add(head);
            head = head.next;
            if(head==null)return false;
        }
        return true;
    }
}

결과 : 성공

Runtime

Memory

이 알고리즘은 시간복잡도가 O(N)이다. ListNode의 길이가 10^4 까지 가능하다고 했다.

그런데 문제 아래에 O(1) 공간복잡도를 사용해서 풀 수 있냐고 적혀있어서 새로운 알고리즘 고민해보았다.

세번쨰 시도 (개선 : 시간 감소)

참고한 사이트 : 토끼와 거북이 알고리즘

다른 방법의 풀이를 찾아보다가 토끼와 거북이 알고리즘을 알게되었다.

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) 은

거북이는 한 칸씩, 토끼는 두 칸씩 앞으로 이동하는데 만약 순환구조가 있다면, 어떻게든 둘이 만나게 될 것이니, 이를 통해 순환여부를 확인할 수 있다는 알고리즘이다.

//토끼와 거북이 알고리즘(fast and slow algorithm)
public class Solution {
    public boolean hasCycle(ListNode head) {       
        if(head==null)return false;

        ListNode tor = head;
        ListNode hare = head;

        while(hare != null && hare.next != null){
            tor = tor.next;
            hare = hare.next.next;

            if(tor == hare)
            return true;
        }
        return false;
    }
}