l*****a
发帖数: 559 | 1 Given a circular linked list, implement an algorithm which returns node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node¡ˉs next
pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C |
d**e
发帖数: 6098 | 2 career cup 150上面关于链表的好像有这题
next
【在 l*****a 的大作中提到】
: Given a circular linked list, implement an algorithm which returns node at
: the beginning of the loop.
: DEFINITION
: Circular linked list: A (corrupt) linked list in which a node¡ˉs next
: pointer points to an earlier node, so as to make a loop in the linked list.
: EXAMPLE
: Input: A -> B -> C -> D -> E -> C [the same C as earlier]
: Output: C
|
l*****a
发帖数: 559 | 3 是上面的。
看不懂答案。：（
【在 d**e 的大作中提到】
: career cup 150上面关于链表的好像有这题
:
: next
|
C*******n
发帖数: 49 | 4 1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
遇，且相遇点在环里
2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
的点就是环的入口点 |
l*****a
发帖数: 559 | 5 这个浅显易懂，谢谢。
【在 C*******n 的大作中提到】
: 1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
: 遇，且相遇点在环里
: 2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
: 3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
: 的点就是环的入口点
|
g**e
发帖数: 6127 | 6 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
比你的方法简单。
【在 C*******n 的大作中提到】
: 1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
: 遇，且相遇点在环里
: 2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
: 3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
: 的点就是环的入口点
|
r******l
发帖数: 10760 | 7 可能永不相遇呢？
【在 g**e 的大作中提到】
: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。
|
c****j
发帖数: 802 | 8 if n is small, they won't meet
【在 C*******n 的大作中提到】
: 1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
: 遇，且相遇点在环里
: 2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
: 3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
: 的点就是环的入口点
|
r*******h
发帖数: 127 | 9 嗯，这个比较简单，，
【在 g**e 的大作中提到】
: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。
|
h******8
发帖数: 278 | 10 怎么确定相遇的是起点？为什么呢？
【在 g**e 的大作中提到】
: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。
|
|
|
g**e
发帖数: 6127 | 11 想一下他们为什么一定相遇在环的起始点
【在 r******l 的大作中提到】
: 可能永不相遇呢？
|
r******l
发帖数: 10760 | 12 根本不能保证相遇，哪来的为什么？
【在 g**e 的大作中提到】
: 想一下他们为什么一定相遇在环的起始点
|
l****c
发帖数: 782 | 13 为什么不能保证相遇呢？是否找了例子呢？
Assume # of the nodes outside the loop is n1, # inside is n2. After you got
the n2, count n2 from the beginning, then the # of left uncounted nodes is
n1. So, even though we do not know n1, we can start to count from the
beginning and from the last counting ending point. After n1 steps, the first
counting process reaches the beginning of the loop, and the second counting
arrives the beginning of the loop, too.
【在 r******l 的大作中提到】
: 根本不能保证相遇，哪来的为什么？
|
r******l
发帖数: 10760 | 14 你说的方法跟那个gate说的完全是两码事啊。
got
first
counting
【在 l****c 的大作中提到】
: 为什么不能保证相遇呢？是否找了例子呢？
: Assume # of the nodes outside the loop is n1, # inside is n2. After you got
: the n2, count n2 from the beginning, then the # of left uncounted nodes is
: n1. So, even though we do not know n1, we can start to count from the
: beginning and from the last counting ending point. After n1 steps, the first
: counting process reaches the beginning of the loop, and the second counting
: arrives the beginning of the loop, too.
|
l****c
发帖数: 782 | 15 哦，我没看他那个方法。。。。
还以为在说我这种方法。。。。
【在 r******l 的大作中提到】
: 你说的方法跟那个gate说的完全是两码事啊。
:
: got
: first
: counting
|
t****t
发帖数: 6806 | 16 你仔细算算就发现, 其实就是一回事---关键是, 第一步相遇的地方就是离开头N步的地
方.
【在 r******l 的大作中提到】
: 你说的方法跟那个gate说的完全是两码事啊。
:
: got
: first
: counting
|
t****t
发帖数: 6806 | 17 你还是看看的好, 他的方法比你的简单.
【在 l****c 的大作中提到】
: 哦，我没看他那个方法。。。。
: 还以为在说我这种方法。。。。
|
c********t
发帖数: 5706 | 18 你的方法好。但最后那个指针，应该是每次移动一步吧？
【在 g**e 的大作中提到】
: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。
|
g**e
发帖数: 6127 | 19 你果然没想
【在 r******l 的大作中提到】
: 根本不能保证相遇，哪来的为什么？
|
w***o
发帖数: 109 | 20 首先，为什么一定会相遇。假设p1是慢指针（每次走一步），p2是快指针（每次走两步
），c是环的起始点，也就是我们要找的点，并且假设环的长度是n。只要有环，p1迟早
要进入环，我们考虑p1进入环以后的情况。在p1完成一圈以前，p2必然超过p1一次。因
为p1完成一圈需要n步，而p2在这段时间内则走了2n步。那么我们考虑p2超越p1时的情
况。假设在这一步p1从节点a移到了节点b。如果p2要不想在节点b与p1相遇而超越b的话
，必然只能在节点a开始往前跳，因为p2每次只移动两步。而它如果从a开始的话，实际
上它们在上一步就已经相遇了。所以，p1和p2必然相遇。
第二点，如何找到c。假设从链表起点到c的距离是k1，从c到相遇点b的距离是k2。相遇
时，p1走了k1 + k2步，p2走了k1 + k2 + cn（c是一个大于0的整数，如果k1很长，而n
很短的话，p2在相遇之前可能已经空转了好几圈）。由于p2速度是p1速度的两倍，我们
有：
2 * (k1 + k2) = k1 + k2 + cn => k1 + k2 = cn
我们要求k1，所以
K1 = cn – k2 = (n – k2) + (c – 1) n
很显然，n – k2是从相遇点b到c的距离。假设k3 = n – k2，就有：
K1 = k3 + c1 * n
意思就是如果一个指针从链表起点走（每次一步），另一个指针从相遇点b转圈（每次
一步），它们必然在环起点c相遇。
很多人忽略了c1*n，虽然对结果没有什么影响，但应该明白，其实环内的指针可能转了
很多圈才与另一个指针相遇的。但不管怎么样它们必然在c相遇。 |
