leetcode 142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。

示例1：

输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。复制代码

示例2：

输入：head = [1,2], pos = 0输出：tail connects to node index 0解释：链表中有一个环，其尾部连接到第一个节点。复制代码

示例3：

输入：head = [1], pos = -1输出：no cycle解释：链表中没有环。复制代码

这道题思路其实很简单，就是快指针每次前进两格，慢指针前进一格，相遇之后将fast置为头结点和slow每次各自前进一格，再次相遇即为环的起始位置。 OK，让我们尝试来证明一下。 首先，我们必须明确一点，如果链表有环，那么快慢指针一定会相遇。来我们看图说话。

我们设环外链表长度为X（当然有可能为0），从环的入口到相遇点的长度为Y，环的周长为C，那么立即推： 快指针走过的长度为 F = X + Y + n*C(n为快指针超了慢指针n圈) 慢指针走过的长度为 S = X + Y 因为： 1.快指针一定走的距离是慢指针的两倍。 2.如果X=0，则快指针正好跑了两圈，而慢指针跑了一圈，此时n=2但并不影响；如果X > 0，快指针总会在第二圈，即n = 1的时候追上慢指针，毕竟快指针先入环总归是比快慢指针同时入环要早一些相遇。（原谅我，这个是我看出来的，但是肯定是可以证明的） 所以： 我们看n=1的情况 X + Y + C = 2 ( X + Y ) 即： X = C - Y 现在我们可以看出来，n=1这种情况下，如果我们有两个指针，一个从头结点开始，一个从快慢指针相遇点开始，同时一步一步地走，那么新的相遇点就是环的入口啦。 特殊的情况n=2时，其实我们可以看到快慢指针相遇点本身就是头结点。那么肯定也是符合最上边的结论的。 上码吧老爷：

func detectCycle(head *ListNode) *ListNode {    slow,fast:=head,head    for{    	//自始至终快慢未相遇，直接跳出就好        if fast==nil||fast.Next==nil {            break;        }        slow, fast = slow.Next,fast.Next.Next        //相遇了就像刚刚说的那样咯        if slow==fast {            fast = head;            for{                if(slow==fast){                    return slow                }                slow=slow.Next                fast=fast.Next            }        }    }    return nil    }复制代码

算法梦想家，来跟我一起玩算法，玩音乐，聊聊文学创作，咱们一起天马行空！