리트코드 - 141. Linked List Cycle

리트코드 - 141. Linked List Cycle

출처 - https://leetcode.com/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 연결 리스트에서 사이클이 있는지 여부를 판별하세요.

연결 리스트에 사이클이 있는 경우, 연속적으로 다음 포인터를 따라가면 어떤 노드든 다시 도달할 수 있습니다. 내부적으로는 pos가 사용되어 꼬리 노드의 다음 포인터가 연결된 노드의 인덱스를 나타냅니다. 주의: pos는 매개변수로 전달되지 않습니다.

연결 리스트에 사이클이 있다면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

 

의사코드

생략

풀이코드

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode turtle = head;
        ListNode rabbit = head;

        while (rabbit != null && rabbit.next != null) {
            rabbit = rabbit.next.next;
            turtle = turtle.next;

            if (rabbit == turtle) {
                return true;
            }
        }
        return false;        
    }
}

코드설명

ListNode가 주어지면 직접 코드 안을 보지 않고 순환되는 구조인지 확인하는 문제다.

여기서는 토끼와 거북이 알고리즘으로 알려진 플로이드의 토끼와 거북이 알고리즘을 사용한다.

 

토끼는 두 걸음씩 가고, 거북이는 한 걸음씩 간다.

만약 빨리 가는 rabbit의 node가 끝에 도달하는 구조라면 null 값이 나와 순환구조를 갖지 않아 false를 리턴한다.

 

만일 node가 null이 아닌 경우 둘은 언젠가 만나는 구조라서 true를 반환한다.

 

시간복잡도 - O(N) (거북이가 끝까지 도착하기 전에 한 번은 무조건 만난다)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

수업에서 봐뒀던 토끼와 거북이 알고리즘 내용이 있어 반가웠으나 처음 봤을땐 링크드리스트를 구현해야 하는 건가 고민했다.

하지만 그런 것은 아니었고 단순하게 토끼와 거북이 알고리즘을 사용하면 되는 문제였다.

 

노드

public class Node<E> {
    public E data;
    public Node<E> next;

    public Node(E data) {
        this.data = data;
        this.next = null;
    }

    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }
}

기본적으로 노드란 데이터를 가지고 있고 다음 노드(next)를 가지는(정확히는 주소값) 데이터 구조이다.

단순히 데이터만 입력되면 다음 노드가 없으므로 null을 가지고, 다음 노드가 있다면 그 노드를 가리킨다.

 

크기를 정하면 바꿀 수 없는 배열과 달리 노드는 재귀적으로 Node에서 Node를 불러 올 수 있으므로 동적 프로그래밍이 가능하다.

단, 배열과 달리 인덱스를 통해 특정 위치에 접근하기 어려운 한계가 있다.

 

링크드리스트의 일종인 노드리스트를 이용하여 접근하는 방법도 있다.

 

종류
Singly Linked List - data와 next를 가지는 노드 타입이고, head와 tail 노드를 통해 값을 추가하거나 변경함
Doubly Linked List - prev, data, next를 가지는 노드 타입으로, dummyHead와 dummyTail을 가지고 노드를 접근함
Circular Linked List - prev, data, next를 가지는 노드 타입으로, dummyHead와 dummyTail을 가지고 있지만 실제로 데이터는 순환구조를 가짐(아직 공부중)

 

정리

노드에 대한 기본적인 접근 방법을 익혔다.

Linked List에 대한 포스팅도 한 번 정리해야 된다.