[1주차] 141. Linked List Cycle

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

Linked List Cycle - LeetCode

---

📝 문제

정의된 해당 LinkedList 의 head 가 주어진다. 해당 LinkedList 가 순환 구조면 true, 순환 구조가 아니면 false 를 리턴하라.

 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
 }

🎈 풀이

문제 설명을 보면 사이클이 마지막 Node 에서 처음이 아닌 중간에 있는 Node로 들어가는 형태로도 사이클이 존재함을 확인할 수 있다.

 

저번 강의 시간에 나왔던 LinkedList 의 순환 판별 문제가 나왔다.

사실 LinkedList 는 워낙 많이 듣고 사용했던 자료구조 이다 보니 익히 알고있는 내용이었으나, 순환구조 판별은 처음 들었다.

애초에 자바 Collection에 정의된 LinkedList 를 사용한다면 이런 문제를 마주할 수 없기 때문이다.

 

강의 시간에 Floid's cycle detection 알고리즘을 배워서 해당 방법을 사용해도 되었으나, 만약 강의를 듣지 않았다면 어떤 알고리즘을 사용했을까 하고 문제를 풀어보았다.

 

노드를 하나씩 거쳐가면서 Set 자료구조에 각 노드의 hashCode를 저장하기로 하였다.

만약 null이 나올때 까지 반복문을 돌렸으나 null 이 나오지 않고 이미 나왔던 hashCode 마주한다면 사이클이 존재하는 것이다.

 

시간복잡도: O(n)

공간복잡도: O(n)

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;
    HashSet<Integer> hashCodeSet = new HashSet<>();
    ListNode node = head.next;
    while (node != null) {
        if (hashCodeSet.contains(node.hashCode())) return true;
        hashCodeSet.add(node.hashCode());
        node = node.next;
    }

    return false;
}

 

 

이번엔 Floid's cycle detection 알고리즘을 사용하였다. O(1) 공간복잡도 이므로 위 알고리즘보다 효율적이다.

 

시간복잡도: O(n)

공간복잡도: O(1)

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

    ListNode slow = head;
    ListNode fast = head;
    do {
        slow = slow.next;
        fast = fast.next;
        if (fast == null) return false;
        fast = fast.next;
        if (fast == null) return false;
    } while (slow != fast);

    return true;
}