链表环与链表交点

1.约瑟夫环问题

示例代码：

---

2. 链表节点

<strong>
解法一：空间O(1) 空间O（M*N）

实现代码：

---

解法二：

---

解法三：

实现代码：

---

3. 判断链表有环

实现代码：

---

4 链表环的起始节点

<strong>思路：解决这道问题的关键就是知道：

举例子：如下图设头结点到链表环起始节点的距离为a,链表环节点数为b,
快指针fast每次走两步，慢指针每次走一步。

可以看到此时a=2,b=6

而且可以知道，每次慢指针走一步，和快指针的差距就加1，因为慢指针和快指针一开始都在头结点，所以：

1. 当慢指针走了a部到达链表环节点时，此时和快指针的距离也为a。
2. 此时快指针和慢指针相聚（b-a），所以快指针还需要走(b-a)次才能追上慢指针。
3. 这也意味着，慢指针要从链表环节点开始走（b-a）步就和快指针相遇。

4. 此时从链表环开始节点已经走了(b-a)步，所以再走b-(b-a)=a步就可以回到链表环节点。

   
   
   
   

   所以：

   
   
   解题思路：根据以上结论，先测定是否有环，找到快慢指针的相遇节点，然后定义另一个指针为头节点，从头结点和相遇节点开始向后遍历，不断判断是否相同，得到相同的节点就是链表环开始结点！
   

---

5. 寻找重复元素

   
   
   
   

   暴力求解法：

   
   
   

---

哈希表法

---

数组环法
对于一个给定数组我们可以可以看成一个个节点，数组下标表示当前节点的值，而其对应的数组值可以看做节点的next，把该值当做数组下标可以找到下一个“节点值”

对于数组下标【0到n+1】的数组，如若往里边填入【0到n】个数，而且不重复。从大的数组下标开始可以得到一条不带环的链表。

可以看到此时有唯一一个没有对应元素值的数组下标5，里边若对应任何重复元素都将形成链表环。（加入现在填个1）

这个原理也很简单普通无环的链表，每个节点的next值都应该是唯一。但假如给尾节点（next指向为null的节点）指向前边的链表节点（相当于给5添加重复值1），那么链表必将为环。

此时可以知道，链表环起始节点就是，数组里边的重复元素。

---

这里有三个重点需要注意：
一、 够成这样子数组环的关键是加入index的下标最大值为n+1的话，那么对应的元素值最大值应该为n。

假如上图的下标7要是对应元素也是7的话，很明显就变成一个自循环，无法串联其他元素。

二、 链表头结点要从最大数组下标开始，也就是从右往左。因为如果从左往右的话可能无法遍历到所有元素。（假如从0开始）

<strong>这里分两方面来分析：

1. 为什么从最大数组下标开始呢？
   首先我们知道一个链表的头结点时没有前驱节点的，前面我们也知道了对数组下标最大为n+1的数组来说，元素值最大应该为n，前面我们也说了，元素值可以理解为next节点。也就数说没有节点的next值能达到n+1，数组下标为n+1的节点没有所谓的前驱节点，所以必然是头结点。
   而除了下标为n+1的节点都有前驱节点所以从它们开始遍历的话链表将不完整。
2. 即使有若干个字循环的节点，也不影响找到重复元素（会跳过那些非重复自循环的节点）。

理解了以上内容就把这题当做，寻找链表环节点就行啦，注意：题目给的元素值为1_{n,下标对应为0}n，所以在遍历的时候记得减一。
实现代码

（看见这种提交结果最开心了~~）