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; } }