142.Linked List Cycle II
===

###### tags: `Medium`,`Linked List`,`Two Pointers`,`Hash Table`

[142. Linked List Cycle II](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.

**Constraints**:

* The number of the nodes in the list is in the range [0, 10^4^].
* -10^5^ <= `Node.val` <= 10^5^
* `pos` is `-1` or a **valid index** in the linked-list.

**Follow up:** Can you solve it using O(1) (i.e. constant) memory?

### 解答
#### Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return

        def getIntersect(head):
            slow, fast = head, head

            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next

                if slow == fast:
                    return slow

            return
        
        intersect = getIntersect(head)
        if not intersect:
            return

        ptr1, ptr2 = head, intersect
        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next

        return ptr1

>[name=Ron Chen][time=Thr, Mar 9, 2023]

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                while head != slow:
                    head = head.next
                    slow = slow.next
                return head
        return None

> [name=Yen-Chi Chen][time=Thu, Mar 9, 2023]

#### C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto fast = head, slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                while (head != slow) {
                    head = head->next;
                    slow = slow->next;
                }
                return head;
            }
        }
        return NULL;
    }
};

> [name=Yen-Chi Chen][time=Thu, Mar 9, 2023]

#### Javascript

function detectCycle(head) {
  if (head === null) return null;
  let tortoise = head;
  let hare = head;

  do {
    if (hare.next === null || hare.next.next === null) return null;
    tortoise = tortoise.next;
    hare = hare.next.next;
  } while (tortoise !== hare);

  hare = head;

  while (tortoise !== hare) {
    hare = hare.next;
    tortoise = tortoise.next;
  }

  return hare;
}

> [name=Marsgoat][time=Thu, Mar 9, 2023]

### Reference
先從這題做起
https://leetcode.com/problems/linked-list-cycle/

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)