[LeetCode] 141. Linked List Cycle

Linked List Cycle - LeetCode

단일 링크드 리스트에서 Cycle이 있는지 확인하는 문제입니다.

 

재귀함수를 통해 링크드 리스트가 반복이 되는지 확인해봤습니다.

 

실패코드

    static class ListNode {
        int val;
        ListNode next;

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

        public void setNext(final ListNode next) {
            this.next = next;
        }
    }

   HashSet<Integer> arrayList = new HashSet<>();

    public int checkCycle(ListNode head) {
        int ret = 0;

        if (head == null || head.next == null) {
            return 0;
        }
        if (arrayList.contains(head.val)){
            System.out.println("서클입니다~~!  : " + head.val);
            System.out.println(arrayList);
            return 1;
        }

        if (!arrayList.contains(head.val)) {
            System.out.println("없음 " + arrayList);
            arrayList.add(head.val);
        }
        ret += checkCycle(head.next);
        return ret;
    }
    public boolean hasCycle(ListNode head) {
        
        return checkCycle(head) != 0;
    }

 

예제는 맞았지만 히든케이스에서 막혔습니다.

단순히 val값이 같다면 cycle이 되었다고 판단했기 때문입니다.

 

이번에는 val값을 주어지는 범위 이외의 것으로 하였습니다.

10의 5승까지 val값이 주어지니 방문한 노드의 val값을 100,004로 바꾸어 보았습니다.

 

성공코드

int MAX = 100_004;
    public int checkCycle(ListNode head) {
        int ret = 0;

        if (head == null || head.next == null) {
            return 0;
        }
        if (head.val == MAX){
            System.out.println("서클입니다~~!  : " + head.val);
            return 1;
        }
        head.val = MAX;
        ret += checkCycle(head.next);
        return ret;
    }
    public boolean hasCycle(ListNode head) {
//        System.out.println(head.val);
        return checkCycle(head) != 0;
    }

이번엔 맞았습니다.

 

시간복잡도

성공코드의 시간복잡도는 O(n)입니다.

하지만 반복되는 재귀로인해 스택을 여러번 부르고 있습니다.

공간복잡도 또한 늘어나고 있습니다.

 

 

코드 개선

재귀함수를 간단하게 작성한 모범코드를 참고하였습니다.

주의할점은 방문한 노드의 next값을 자기자신으로 바꿔야합니다.

그렇지 않으면 순환이 될때 true를 반환하지 않고 계속 순환하여 무한루프를 돌기 때문입니다. 

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

  

 

다른사람의 풀이

투포인터를 이용하여 접근했습니다.

slow는 한칸씩, fast는 두칸씩 건너면서 서로 같은지 확인하는 코드입니다.

 

public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

 

시간복잡도

O(n)의 시간복잡도입니다.

 

느낀점

재귀를 탐색하여 하는것보다는 투포인터로 2개씩 탐색하는 방법도 있다는 것을 알았습니다.

 

투포인터는 단순히 배열의 값만 아니라, 어떤 자료형이든 2개를 동시에 작업해야한다면 떠올려봐야 할것 같습니다.

 

참고

Linked List Cycle - LeetCode