LeetCode 141번 - Linked List Cycle

문제

주어진 연결 리스트가 순환하고 있는지 확인하는 문제이다.

 

---

살펴보기

문제를 푸는 방법은 여러 가지가 있다고 하는데

 

2개의 포인터를 이용하는 방법(투 포인터 알고리즘)이 가장 자주 쓰이는 것 같고,

컬렉션을 이용하는 방법도 많이 쓰이는 것 같다.

 

 

먼저 포인터를 이용하는 방법은 head와 연결된 두 노드를 활용한다.

 

한 노드는 한 칸씩(.next), 다른 노드는 한번에 두 칸씩(.next.next) 이동시킨다.

리스트가 순환하고 있다면, 두 노드가 순회하다가 만나게 된다!

그러나 순환하고 있지 않다면 null을 만나서 순회가 끝나게 된다.

 

 

컬렉션을 이용하는 방법은 간단하다.

컬렉션을 하나 만들고, 컬렉션에 방문한 노드의 주소값을 저장해둔다.

그리고 노드를 방문할 때마다 컬렉션에 해당 노드의 주소값과 동일한 값이 있는지 확인하면 된다.

 

순환하는 연결 리스트인 경우, 노드를 순회하다 보면 컬렉션에서 노드의 주소값과 동일한 값을 찾을 수 있다.

반면 순환하지 않는 경우, 동일한 값을 찾지 못하고 null을 만나서 순회가 종료된다.

 

---

풀어보기

먼저 포인터를 이용하는 방법이다.

 

slow와 fast 노드를 생성해 slow는 한 칸씩, fast는 두 칸씩 이동시켰다.

if(head == null) return false;

ListNode slow = head;
ListNode fast = head;

while(slow != null && fast != null && fast.next != null){         
    slow = slow.next;
    fast = fast.next.next;

    if(slow == fast) return true;     
}

return false;

 

다음으로 컬렉션을 이용하는 방법이다.

 

먼저 값을 저장할 set를 선언했다.

set에 현재 노드의 참조값이 있는지 확인해서 있으면 true를 반환하고,

없으면 set에 현재 노드의 참조값을 저장한 다음, 다음 노드로 이동했다.

Set<ListNode> set = new HashSet<>();

while(head!=null){
    if(set.contains(head)) return true;
    set.add(head);
    head = head.next;
}

return false;

 

제출 결과를 보면

 

속도는 포인터를 이용하는 방법이 훨씬 빨랐다.  (포인터 : 0ms / 컬렉션 : 5ms)

메모리 사용량은 컬렉션을 이용하는 방법이 약간 더 적었다 (포인터 : 43.5MB / 컬렉션 : 42.7MB)