[Medium] 142. Linked List Cycle II

Leetcode 142

Leetcode 142번 문제에서는 Linked List가 주어지고, 주어진 Linked List에서 cycle이 발생하는지 알아내고, 발생하면 발생 지점의 노드를 반환하고, cycle이 발생 하지 않으면 null를 return해주면 된다. 

 

#풀이 

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet hs = new HashSet();
        boolean dup = false;
        while(head != null){
            if(!hs.add(head)){ //HashSet에 add가 중복이 발생해 false return시 현재노드 반환
                return head;
            }
            head = head.next;
        }
        return null;
    }
}

이 풀이는 Hashset을 이용한 풀이이다. Set의 특성은 중복된 데이터가 있을 수 없다는 점이다. 그 점을 이용하여 문제를   풀수 있다. 연결 리스트를 순회하면서 Hashset에 각 노드를 추가 해주면 된다. 만약 Hashset.add가 false를 반환하면 현재 노드를 return시켜 주면 된다. 만약 아무런 문제 없이 노드 들을 다 순회하였다면  중복 노드가 없었다는 뜻이기에 null을 return시켜주면 된다.

 

public class Solution {
            public ListNode detectCycle(ListNode head) {
            ListNode fast = head, slow = head;
            while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
            ListNode slow2 = head;
            while (slow != slow2){
                slow2 = slow2.next;
                slow = slow.next;
                 }
                return slow;
                }
            }
            return null;
           }
        }

다음 풀이는 플로이드의 토끼와 거북이 알고리즘이다. 노드를 1칸씩 순회하는 노드 reference, 즉 거북이 reference와 2개씩 순회하는 reference, 즉 토끼 reference 를 이용해 순회 시켜준다, 만약 토끼 노드와 거북이 노드가 만난다면, cycle이 발생했다는 뜻이기에 slow2 노드를 생성해 slow노드와 다시 만날 때까지 순회 시켜주고, 만나는 지점을 return하면 된다.