:orphan:

Linked List Cycle
=================

.. highlight:: none

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

Given ``head``, the head of a linked list, determine if the linked list
has a cycle in it.

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. **Note that ``pos`` is not
passed as a parameter**.

Return ``true`` *if there is a cycle in the linked list*. Otherwise,
return ``false``.

 

**Example 1:**

|image1|

::


   Input: head = [3,2,0,-4], pos = 1
   Output: true
   Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2:**

|image2|

::


   Input: head = [1,2], pos = 0
   Output: true
   Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

**Example 3:**

|image3|

::


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

 

**Constraints:**

- The number of the nodes in the list is in the range
  ``[0, 10``\ :sup:```4```\ ``]``.
- ``-10``\ :sup:```5```\ ``<= Node.val <= 10``\ :sup:```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?

.. |image1| image:: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png
.. |image2| image:: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png
.. |image3| image:: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png

.. highlight:: python

Pattern
-------
Hash Table, Linked List, Two Pointers

Solution
--------
Set two pointers, ``a`` and ``b``, to ``head``. Move ``a`` 1 node at a time but
move ``b`` 2 nodes at a time. If ``a`` and ``b`` ever point to the same node,
then ``b`` must have wrapped around the linked list and caught up to ``a``.

Code
----

.. literalinclude:: ../problems/easy/linked-list-cycle/linked_list_cycle__approach_1.py
    :language: python
    :lines: 16-

Test
----
>>> from linked_list_cycle__approach_1 import ListNode, hasCycle
>>> head = ListNode.from_list([3, 2, 0, -4])
>>> head.next.next.next.next = head.next
>>> hasCycle(head)
True
>>> head = ListNode.from_list([1, 2])
>>> head.next.next = head
>>> hasCycle(head)
True
>>> head = ListNode.from_list([1])
>>> hasCycle(head)
False

Complexity
----------
| :math:`n` is the number of nodes in the linked list
| Time: :math:`O(n)` — pointers will reach end or meet after at most :math:`n` steps
| Auxiliary Space: :math:`O(1)` — 2 pointers only

.. autoclass:: linked_list_cycle__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: linked_list_cycle__approach_1.hasCycle