้ข็ฎๆ่ฟฐ

``````Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: 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.

Follow-up:
Can you solve it without using extra space?``````

ไปฃ็ 

Approach #1 Hash Table

``````/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
Set<ListNode> visited = new HashSet<ListNode>();

while (node != null) {
if (visited.contains(node)) {
return node;
}
node = node.next;
}

return null;
}
}``````

Approach 2: Floyd's Tortoise and Hare

``````public class Solution {
if (head == null)  return null;

if (intersect == null)     return null;

ListNode ptr2 = intersect;
while (ptr1 != ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1;
}

// A fast pointer will either loop around a cycle and meet the slow
// pointer or reach the `null` at the end of a non-cyclic list.
while (hare != null && hare.next != null) {
tortoise = tortoise.next;
hare = hare.next.next;
if (tortoise == hare) {