LeetCode 142 环形链表 II python

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

说明：不允许修改给定的链表。

样例

1如果不是环，则输出None
2如果是环，则输出入口节点

想法：
通过ac141，知道慢节点循环的次数就是环的长度
无环的情况不用考虑，直接返回None即可
有环分为下面两种可能

这种情况就是链表正好构成一个环

第二种情况就是链表中存在环，由上图可知快节点走过的路径是a,b,c,d,b,c；慢节点走过的路径是a,b,c
又因为快节点速度是慢节点的两倍，所以可知

1a+b+c+d+b+c = 2a+2b+2c
2d+b+c = a+b+c
3d(相遇点距环入口的距离) = a(头节点距环入口的距离)

再看第一种情况，可以知道，快节点是慢节点的多少倍，快节点就通过多少圈与慢节点相遇。
所以就根据相遇点距环入口的距离等于头节点距环入口的距离

1class Solution(object):
2    def detectCycle(self, head):
3        """
4        :type head: ListNode
5        :rtype: ListNode
6        """
7        if head is None:
8            return None
9        if head.next is None:
10            return None
11        first = second = head
12        while second.next and second.next.next:
13            first = first.next
14            second = second.next.next
15            if first == second:
16                p = head
17                while first != p:
18                    p = p.next
19                    first = first.next
20                return p
21        return None

最后

刷过的LeetCode源码放在Github上了，希望喜欢或者觉得有用的朋友点个star或者follow。
有任何问题可以在下面评论或者通过私信或联系方式找我。
联系方式
QQ：791034063
Wechat：liuyuhang791034063
CSDN：https://blog.csdn.net/Sun_White_Boy
Github：https://github.com/liuyuhang791034063