【题目描述】
Given a linked list, return the node where the cycle begins.
If there is no cycle, returnnull.
给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。
【题目链接】
www.lintcode.com/en/problem/linked-list-cycle-ii/
【题目解析】
此题不仅要求判断是否存在环,同时还需要在存在环的情况下找出环的起始节点。这就比I要难一些。最开始我想到的方法还是跟上题类似,一个fast ,每次移动两步,一个slow,每次移动一步。两个指针不仅要向前移动,同时还需要记录各自走的步数(fastCount和slowCount)。当相遇的时候,fastCount减去slowCount就是换的长度(假设这个长度的len)。这个时候让fast和slow重新指向head节点。然后先让fast指针向前移动len步。之后fast和slow再同时移动,两个每次均移动一步。当两者相遇的时候就是环的其实节点。
【参考答案】