[Leetcode Top Interview 150] 141. Linked List Cycle

난이도 : easy

 

문제링크

• 링크드리스트의 사이클 여부를 리턴하라

 

1. 접근법

• head로 linked list를 순회하면서 hashSet의 값을 가리킨다면 사이클

 

2. 의사코드

Set<Node> hashSet = new HashSet<>();

while (head.next != null) {
	if (hashSet에 노드가 없다면) {
    	hashSet에 노드 추가
    } else {
		return true;
    }
	head 한칸 이동
}

return false;

 

3. 구현 코드

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

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

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

        return false;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - n번 원소를 반복하므로
• 공간복잡도 : O(n) - n개 원소만큼 hashSet이 가지고 있음

 

5. 개선점

모르겠다

(공간복잡도를 줄일 수 있나..? 캐싱해야 하지 않나?)

 

6. 회고

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

        ListNode slow = head;
        ListNode fast = head.next;

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

            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

(출처 : NickWhite)

 

투포인터를 이용하여 사이클 여부를 판단할 수 있다

 

slow: 한칸씩 이동

fast : 두칸씩 이동

 

slow와 fast가 일치하지 않을때까지 반복시킨 후

• fast == null 혹은 fast.next == null이면 사이클이 아님
• slow와 fast가 일치하면 사이클

이렇게 하면 공간복잡도를 O(1)로 줄일 수 있다