Lintcode103 Linked List Cycle || solution 题解

【题目描述】

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再同时移动,两个每次均移动一步。当两者相遇的时候就是环的其实节点。

【参考答案】

www.jiuzhang.com/solutions/linked-list-cycle-ii/

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容