[LeetCode] 142. Linked List Cycle II - 깊이우선탐색(DFS) JAVA

https://leetcode.com/problems/linked-list-cycle-ii/description/

코드설명

깊이우선탐색(DFS) 를 활용합니다.

 

말그대로, 깊이우선탐색을 하며, 이미 방문한 공간은 더 이상 방문하지 않도록 하면 됩니다.

저의 경우, 100000 + 1 이상의 숫자로 방문했다면 처리했습니다.

 

다른 방법으로는 HashSet을 사용하는 방법이 있습니다. 1번방법과 사실 같습니다만, 별도의 메모리 공간을 사용한다는점이 다릅니다.

코드

정답코드1입니다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    int visitedStart = 100000 + 1;
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(-100000 - 1);
        dummy.next = head;
        int visitedTemp = visitedStart + 1;
        while(head != null){
            if(head.val >= visitedStart) {
                return head;
            }
            head.val = visitedTemp++;
            head = head.next;
        }
        return null;
    }
}