LeetCode - 142. Linked List Cycle II(LinkedList, HashTable, Two Pointers)***

문제

링크된 목록의 선두를 지정하면 사이클이 시작되는 노드를 반환합니다. 사이클이 없을 경우 null을 반환합니다.
목록에 다음 포인터를 계속 따라가면 다시 도달할 수 있는 노드가 있는 경우 링크된 목록에 사이클이 있습니다. 내부적으로 pos는 테일 다음 포인터가 연결되어 있는 노드의 인덱스를 나타내기 위해 사용됩니다(0-indexed). 사이클이 없으면 -1입니다. pos는 파라미터로 전달되지 않습니다.
링크된 목록을 수정하지 마십시오.

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

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 1:

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.

Example 2:

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.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

풀이

자바입니다.

• Floyd's Cycle 알고리즘을 사용합니다.
  알고리즘 설명1 - https://www.youtube.com/watch?v=Cs3KwAsqqn4
  알고리즘 설명2 - https://neurowhai.tistory.com/384
  풀이 - https://leetcode.com/problems/linked-list-cycle-ii/discuss/1701128/C%2B%2BJavaPython-Slow-and-Fast-oror-Image-Explanation-oror-Beginner-Friendly

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
               slow = head;
                while (slow !=fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            } 
                
        }
        
        return null;
    }
}

풀이 자체는 어렵지 않지만 Floyd's Cycle 알고리즘의 원리를 이해하기 어려웠습니다.