[Java] LeetCode 142. Linked List Cycle II

[Java] LeetCode 142. Linked List Cycle II

 

문   제 : 

링크드리스트가 주어진다.

사이클이 존재 하지 않으면 null,

사이클이 존재하면 사이클이 시작하는 노드를 반환하여라.

 

Constraint

{ The number of the nodes in the list is in the range [0, 104] }

{ -10^5 <= Node.val <= 10^5 }

{ pos is -1 or a valid index in the linked-list. }

 

Given the head of a linked list, return the node where the cycle begins.
If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed).
It is -1 if there is no cycle. 
Note that pos is not passed as a parameter.
Do not modify the linked list.

 

Example )

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: 
There is a cycle in the linked list, where tail connects to the second node.

//////////////////////////////////////////////////////////

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: 
There is a cycle in the linked list, where tail connects to the first node.

 

---

접   근 : 

Hash Set 을 이용한 중복 노드 검사

---

해   결 : 

head부터 HashSet에 추가해가면서 중복된 노드가 추가되고 있는지 확인한다.

HashSet은 중복된 값을 저장하지 않는다. -> 중복된 값을 add하면 false를 반환해준다.

만약 false가 반환된다면, 그 부분이 사이클의 첫 시작 노드이다. 

끝까지 갔는데도 사이클을 발견하지 못했다면, null을 반환한다.

---

결   과  :

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();

        while(head != null){
            if(!set.add(head)){
                return head;
            }
            head = head.next;
        }
        return null;
    }
}