linked-list-cycle-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given the <code>head</code> of a linked list, return the node where the cycle begins. If there is no cycle, return <code>null</code>.

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 <code>next</code> pointer. Internally, <code>pos</code> is used to denote the index of the node that tail&#39;s <code>next</code> pointer is connected to (0-indexed). It is <code>-1</code> if there is no cycle. Note that <code>pos</code> is not passed as a parameter.

Do not modify the linked list.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png" style="height: 145px; width: 450px;" />
<pre>
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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png" style="height: 105px; width: 201px;" />
<pre>
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.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png" style="height: 65px; width: 65px;" />
<pre>
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of the nodes in the list is in the range <code>[0, 104]</code>.</li>
	<li><code>-105 &lt;= Node.val &lt;= 105</code></li>
	<li><code>pos</code> is <code>-1</code> or a valid index in the linked-list.</li>
</ul>

&nbsp;
Follow up: Can you solve it using <code>O(1)</code> (i.e. constant) memory?

detectCycle

Linked List Cycle II

Linked List Cycle

linked-list-cycle

环形链表

Find the Duplicate Number

find-the-duplicate-number

寻找重复数

Hash Table

Linked List

Two Pointers

给定一个链表的头节点 &nbsp;<code>head</code>&nbsp;，返回链表开始入环的第一个节点。&nbsp;如果链表无环，则返回&nbsp;<code>null</code>。

如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。注意：<code>pos</code> 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

<ul>
</ul>

&nbsp;

示例 1：

<img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png" />

<pre>
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
</pre>

示例&nbsp;2：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png" />

<pre>
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
</pre>

示例 3：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png" />

<pre>
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
</pre>

&nbsp;

提示：

<ul>
	<li>链表中节点的数目范围在范围 <code>[0, 104]</code> 内</li>
	<li><code>-105 &lt;= Node.val &lt;= 105</code></li>
	<li><code>pos</code> 的值为 <code>-1</code> 或者链表中的一个有效索引</li>
</ul>

&nbsp;

进阶：你是否可以使用 <code>O(1)</code> 空间解决此题？