r****o
发帖数: 1950 | 1 刚才看到有人的面经里面有这个题目。
有谁有什么好办法吗？
我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
这个方法时间复杂度和空间复杂度都是O(n),
有谁有更好的方法吗？ |
f*******e
发帖数: 1161 | 2 跟找环算法一样，只是再往前推进一个节点
【在 r****o 的大作中提到】
: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？
|
r****o
发帖数: 1950 | 3 找环算法怎么返回环的位置?
【在 f*******e 的大作中提到】
: 跟找环算法一样，只是再往前推进一个节点
|
f*******e
发帖数: 1161 | 4 你用的是哪个找环算法
【在 r****o 的大作中提到】
: 找环算法怎么返回环的位置?
|
r****o
发帖数: 1950 | 5 你说你用的哪一种吧，我这里没有找环，不过单链表反转可以用来找环。
【在 f*******e 的大作中提到】
: 你用的是哪个找环算法
|
f*******e
发帖数: 1161 | 6 两个指针，一个跨一步，一个跨两步，当相交时就是环的"尾巴"
【在 r****o 的大作中提到】
: 你说你用的哪一种吧，我这里没有找环，不过单链表反转可以用来找环。
|
r****o
发帖数: 1950 | 7 你这个环的尾巴是怎么定义的？
假定一个单链表,1->2->3->4->5->6->7 7又指向5
fast: 1->3->5->7->6->5->7->6...
slow: 1->2->3->4->5->6->7->5...
两者在7相遇，
再假定一个单链表,1->2->3->4->5->6->7->8 8又指向5
fast: 1->3->5->7->5->7->5->7...
slow: 1->2->3->4->5->6->7->8...
两者在5相遇，
这两者相遇的地方没规律。
在 feelalone (感到孤独) 的大作中提到: 】 |
f*******e
发帖数: 1161 | 8 看来我搞错了，还得再研究下
感觉应该是这个思路吧？
【在 r****o 的大作中提到】
: 你这个环的尾巴是怎么定义的？
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7->6...
: slow: 1->2->3->4->5->6->7->5...
: 两者在7相遇，
: 再假定一个单链表,1->2->3->4->5->6->7->8 8又指向5
: fast: 1->3->5->7->5->7->5->7...
: slow: 1->2->3->4->5->6->7->8...
: 两者在5相遇，
: 这两者相遇的地方没规律。
|
f****4
发帖数: 1359 | 9 找环的算法后面还有一部分
当fast和slow相遇之后
fast remove到head，然后每次 move 1 step，当fast和slow再次相遇就是环的开始节
点。得到这个节点N，你再遍历一下list，如果当前节 |
r****o
发帖数: 1950 | 10 多谢。
但是如果fast指针后来也每次move 1 step，那就跟slow 指针速度一样了。
感觉这样的话，有可能两个指针慢悠悠的转圈，但是就是不相遇啊。
【在 f****4 的大作中提到】
: 找环的算法后面还有一部分
: 当fast和slow相遇之后
: fast remove到head，然后每次 move 1 step，当fast和slow再次相遇就是环的开始节
: 点。得到这个节点N，你再遍历一下list，如果当前节
|
|
|
f****4
发帖数: 1359 | 11 fast remove到list head
你google一下吧，可以证明他们相遇点是环开始的
【在 r****o 的大作中提到】
: 多谢。
: 但是如果fast指针后来也每次move 1 step，那就跟slow 指针速度一样了。
: 感觉这样的话，有可能两个指针慢悠悠的转圈，但是就是不相遇啊。
|
r****o
发帖数: 1950 | 12 奇怪，看看这个例子，
假定一个单链表,1->2->3->4->5->6->7 7又指向5
fast: 1->3->5->7->6->5->7
slow: 1->2->3->4->5->6->7
两者在7相遇，
相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
fast: 1->2->3->4->5->6->7...
slow: 5->6->7->5->6->7->5...
好像永远都不会相遇啊。是不是我哪儿理解得不对?
【在 f****4 的大作中提到】
: fast remove到list head
: 你google一下吧，可以证明他们相遇点是环开始的
|
f*******e
发帖数: 1161 | 13 在7相遇
fast: 7 5 6 7 5 6 7
slow: 1 2 3 4 5 6 7
【在 r****o 的大作中提到】
: 奇怪，看看这个例子，
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7
: slow: 1->2->3->4->5->6->7
: 两者在7相遇，
: 相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
: fast: 1->2->3->4->5->6->7...
: slow: 5->6->7->5->6->7->5...
: 好像永远都不会相遇啊。是不是我哪儿理解得不对?
|
H*X
发帖数: 281 | 14 我记得有个数学推导，相遇之后，能算出来环从哪开始的 |
y**i
发帖数: 1112 | 15 我有一个idea，你看行不行？
当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
要的结果了。这个方法也同样适用于找环的初始结点。
【在 r****o 的大作中提到】
: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？
|
r****o
发帖数: 1950 | 16 这个方法不错，多谢。
【在 y**i 的大作中提到】
: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。
|
y**i
发帖数: 1112 | 17 不客气，互相交流，共同进步！
【在 r****o 的大作中提到】
: 这个方法不错，多谢。
|
f****4
发帖数: 1359 | 18 slow 7->5->6->7->5->6->7
slow没有动
这个方法用来找到环开始的节点，可以用来解变体
找到环中第m个节点
【在 r****o 的大作中提到】
: 奇怪，看看这个例子，
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7
: slow: 1->2->3->4->5->6->7
: 两者在7相遇，
: 相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
: fast: 1->2->3->4->5->6->7...
: slow: 5->6->7->5->6->7->5...
: 好像永远都不会相遇啊。是不是我哪儿理解得不对?
|
d*******d
发帖数: 2050 | 19 先找到环的起点,然后从头再来,第一次出现p->next==环起点的时候即可。
【在 r****o 的大作中提到】
: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？
|
s******9
发帖数: 84 | 20 怎么找这个交点呢？
【在 y**i 的大作中提到】
: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。
|
|
|
m*****g
发帖数: 226 | 21 assume when fast meet slow for the first time, slow has travelled D+L, fast
has travelled D+L+kS
D is from list head to the beginning of loop, L is from beginning of loop to
this position, which is a portion of the loop length, k is any positive int
, S is loop length.
since the time was same, we have (D+L)/1 = (D+L+kS)/2
we get D = kS-L = (k-1) S + (S-L)
So if we let another ptr (fast) to start from head with same speed as slow,
when it travels D, the slow would have travelled (k-1)S + (S-L), w |
j**l
发帖数: 2911 | 22 这个CareerCup的150题收录了，解答比较清楚 |
m********g
发帖数: 692 | 23 咋搞这复杂咛? 为啥弄俩小 破恩特 追着玩?
没空间要求的话. 整个list中, 只有一个地址被用了两次, 就是环的起点. 线性遍历把
地址(reference)扔hash里 O(1), 冲突了就找到了. total O(n)
这样处理有啥毛病么?
【在 y**i 的大作中提到】
: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。
|
y**i
发帖数: 1112 | 24 没啥毛病，hacking a google interview中我记得讲过，有的面试官喜欢hash，有的
hate hash，如果你正好碰上了后者，那是不是还要准备另一种解法？
【在 m********g 的大作中提到】
: 咋搞这复杂咛? 为啥弄俩小 破恩特 追着玩?
: 没空间要求的话. 整个list中, 只有一个地址被用了两次, 就是环的起点. 线性遍历把
: 地址(reference)扔hash里 O(1), 冲突了就找到了. total O(n)
: 这样处理有啥毛病么?
|
