[每日一题]142.Linked List Cycle II（链

1.这是一个判断 链表中是否有环 的题目．是昨天那个题目的衍生，判断环在哪个地方．

链接：https://leetcode.com/problems/linked-list-cycle-ii/

142. Linked List Cycle II.JPG

题目的意思就是输入一个链表，然后判断链表是否构成了环状结构，并且找出环结构的位置。

这里有两个思路解决这个问题：

**
1.使用键值对，记录这个Node，发现相同直接返回这个值就可以了。ps：其实集合（Set就可以，插入错误，直接判断有环）
2.使用长短指针的思路。先判断是否有环，然后根据相关信息计算出环的位置，下面详细解释。**

2.题解：

给出以上两个思路的代码：
思路1：

class Solution:
    # 2- 使用字典记录
    def hasCycle(self, head):
        dict_list = {}
        i = 0
        node = head
        while node:
            if node in dict_list:
                return "tail connects to node index " + str(dict_list[node]) # 这里可以直接返回在哪个节点形成环
            else:
                dict_list[node] = i  # 记录键值对
                i += 1
                node = node.next
        return "no cycle"

思路3：
详细解释：
1.首先通过长短指针判断是否有环，如果有的执行下一步，没有的话，返回“no cycle”
2.假设 到入口的距离是H，环的长度是C，第一次相遇的位置是D。
因此，慢指针的距离是

dis_slow = H+mC+D，m为自然数

快指针的距离是

dis_fast = H+nC+D，m为自然数

因为快指针运动的步长是慢指针的两倍，因此，得到以下的这个公式。

2*dis_slow = dis_fast 
H = (n-2m)C - D

将n-2m用k代替

H =kC - D

3.让慢指针回到head节点，和fast同时以步长为1的速度跑。此时，等他们两相遇时候，慢节点运动H，快节点运动KC-D的长度。此时返回H节点位置即可。

画图解释：

142. Linked List Cycle II.JPG

  # 3- 使用长短指针记录
    def hasCycle(self, head):
        # 1.判断是否有环
        try:
            fast = head.next.next
            slow = head.next
            while slow != fast:
                slow = slow.next
                fast = fast.next.next
        except:
            return "no cycle"
        # 2 根据公式计算出对应的环开始的位置
        slow = head
        i = 0
        while slow is not fast:
            slow, fast = slow.next, fast.next
            i += 1
        return "tail connects to node index " + str(i)

不过这一题，有个坑，这个不是直接返回字符串，而是返回，Ｎone或者节点．

3.完整代码

查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/edit/master/1-List/142-Linked-List-Cycle-II.py