[Java] 141. Linked List Cycle

문제 파악

연결 리스트의 헤드가 주어진다. 그리고 이 연결 리스트가 사이클을 이루는지 결정해야한다.

 

---

풀이

 

1️⃣ Set 자료구조를 이용한 풀이

 

💡 떠오른 Idea

노드를 set 자료구조에 입력하고, 다음 노드로 진행하기 전에

진행할 노드가 set에 입력되어있는지 확인한다.

진행할 노드가 set에 입력되어있었다면, 사이클임을 알 수 있다.

 

위 아이디어를 바탕으로 코드를 작성하였다.

 

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode now = head;
        set.add(now);

        while (now != null) {
            ListNode nextNode = now.next;

            if (set.contains(nextNode)) {
                return true;
            }

            set.add(nextNode);
            now = nextNode;
        }

        return false;
    }
}

 

결과

결과를 확인해보니, 속도 개선이 필요해보였다.

 

또한, 공간 복잡도 O(1) 풀이 방법이 존재한다고 하여 고민해보았다.

 

2️⃣ 플로이드 순환 찾기 알고리즘

 

처음 알게된 알고리즘이다.

 

속도가 다른 두개의 포인터를 루프에 진입시켰을 때, 사이클이라면 동일한 노드를 가리키는 시점이 생긴다는 아이디어를 이용한 알고리즘이다.

 

포인터의 속도가 1인 거북이와 속도가 2인 토끼가 루프를 순회하다보면 같은 값을 가리키는 지점이 반드시 생기는 것을 예로 들 수 있다.

 

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode pointer1 = head;
        ListNode pointer2 = head;

        while (pointer2.next != null && pointer2.next.next != null) {
            pointer1 = pointer1.next;
            pointer2 = pointer2.next.next;

            if (pointer1 == pointer2) {
                return true;
            }

        }
        return false;
    }
}

 

결과

---

📖 회고

이번 문제에서도 내가 알고있는 방식으로도 해결할 수 있었지만, 효율적인 새로운 알고리즘 방법을 알게 되었다.

 

처음에는 이런 생소한 알고리즘 기법이 부담스러웠었는데, 알아가는 재미가 생긴 것 같고 이러한 기법을 만든 사람들이 참 대단하다는 생각이 들었다.

 

머릿속에 잘 기억해두어야겠다.