个人中心
文章发布
退出
作者热门文章
- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用？
- database - RESTful URI 是否应该公开数据库主键？
25
4
<分区>
从 Cracking the Coding Interview 中，有一个练习说:
给定一个循环链表，实现一个返回循环开始处的节点的算法。
循环链表的定义:一个(损坏的)链表，其中一个节点的下一个指针指向一个较早的节点，从而在链表中形成一个循环。
算法的答案基本上是使用慢跑者和快跑者来遍历链表，看看它是否循环。如果慢跑者和快跑者发生碰撞，它就会循环，所以你会找到循环开始处的节点。 (如果他们不碰撞，那么跑得快的人最终会到达链表的末尾，这意味着没有循环。)
但是这本书关于查找循环开始处节点位置的答案依赖于链表具有大小为 k 的“非循环”部分的假设。一旦慢跑者和快跑者发生碰撞，你就将慢跑者移到链表的头部。您以相同的速度迭代两者，直到它们发生碰撞。它们碰撞的地方是循环开始的节点。
我的问题是，是否可以在不假设链表具有大小为 k 的“非循环”部分的情况下找到循环开始处的节点的位置？或者我是否必须假设有一个大小为 k 的“非循环”部分？
25
4
0
我是一名优秀的程序员,十分优秀！