t********e
发帖数: 25 | 1 #1 There is a linked list. The last node could point back to any node in
the list (including the head). Find the node in the list to which the last
node points. Or in other words at which node does the circular linked list
start.
think of a O(n) solution with O(1) space, or space efficient.
We all know how to detect the cycle.
for O(n^2) solution is also easy. just move the pointer from head to the
next, and loop the cycle.
I was thinking break up the link list in loop for O(n) solution.
Any so | H*M
发帖数: 1268 | 2 1->2->3->4->5->6->7->8->(6,going back)
first find the length of the loop,here it is 3
then put two pointers, one at 1, another one at 1+3 =4
当两者第一次相遇的时候,那个node就是loop的start
【在 t********e 的大作中提到】
: #1 There is a linked list. The last node could point back to any node in
: the list (including the head). Find the node in the list to which the last
: node points. Or in other words at which node does the circular linked list
: start.
: think of a O(n) solution with O(1) space, or space efficient.
: We all know how to detect the cycle.
: for O(n^2) solution is also easy. just move the pointer from head to the
: next, and loop the cycle.
: I was thinking break up the link list in loop for O(n) solution.
: Any so
| t********e
发帖数: 25 | | H*M
发帖数: 1268 | 4 不谢.
给你一题: 请证明为什么用两个指针一快一慢必定可以找出loop
【在 t********e 的大作中提到】
: Right. 3x.
| t********e
发帖数: 25 | 5 Since their relative distance in the loop are getting smaller 1 each time.
faster one will catch up with slower one for sure. | l**a
发帖数: 43 | 6 find the max of the linked list, set the loop nodes' value to max+1, scan fr
om head for the first node whose value is max+1, it is the loop start
【在 t********e 的大作中提到】
: #1 There is a linked list. The last node could point back to any node in
: the list (including the head). Find the node in the list to which the last
: node points. Or in other words at which node does the circular linked list
: start.
: think of a O(n) solution with O(1) space, or space efficient.
: We all know how to detect the cycle.
: for O(n^2) solution is also easy. just move the pointer from head to the
: next, and loop the cycle.
: I was thinking break up the link list in loop for O(n) solution.
: Any so
| r**u
发帖数: 1567 | 7 "set the loop nodes' value to max+1", what does this mean? What do you mean
by "loop nodes"?
fr
【在 l**a 的大作中提到】
: find the max of the linked list, set the loop nodes' value to max+1, scan fr
: om head for the first node whose value is max+1, it is the loop start
| h*********e
发帖数: 56 | 8 怎么确定loop的长度呢？
【在 H*M 的大作中提到】
: 1->2->3->4->5->6->7->8->(6,going back)
: first find the length of the loop,here it is 3
: then put two pointers, one at 1, another one at 1+3 =4
: 当两者第一次相遇的时候,那个node就是loop的start
| H*M
发帖数: 1268 | 9 最简单的，
在你确定有没有圈，用两个指针，他们预见的时候，你不是知道有loop了吗，然后keep
这个Node*,把快的或者慢的再走一圈再次碰到这个 Node*就可以了
【在 h*********e 的大作中提到】
: 怎么确定loop的长度呢？
| h*********e
发帖数: 56 | |
|
