生产code寻找一个链表结 [英] Production code for finding junction in a linked list
问题描述
有人问我这个问题，在一些采访。
我被要求写code寻找结在一个链表（这是在的Y用双臂不一定相等的形式），用于生产环境中的O（1）空间和线性时间。
我想出了这个解决方案（我曾previously看到的地方）：
两个列表1.测量长度，让他们成为L1和L2 （L1-L2）| 2.移动大名单指针|。 3.现在一起移动两个三分球，如果它们指向同一个位置， 即结。
记者：你的code将如何处理？
案例1. Y型格式链表有环的交界处后结束。
情况2.任何输入列表的是环状和他们不合并。
案例3，Y型格式列表中有环路路口前结束。
在应对一种情况下，我的回答是：
我会发现，在使用两个指针列表中的循环（一个快速和慢速），测量长度在这两个指针必须满足该节点，然后执行previous情况。然而，对于案件2和3，我能找出没有更好的解决办法比当检测到循环（使用2-pointer技术）优雅地退出。
我相信有这个problem.Please更好的答案下拉你：）
谢谢
该问题是由面试官的（似乎）犯了难除pretation了如下的形状也被认为是有效的：
A \ _____ A \ ___
\ / \ \ / \
\ / \ \ /
+ - + -------------
/ P /
/ /
B / B /
即。有一路口但随后的列表循环返回到一个地方之前或结之后。计算所述列表的长度的过程不直接的帮助，因为环状列表的长度是不确定的。
首先要注意的循环在循环列表末尾的长度可以通过此操作系统的计算（1）内存/ O（n）的时间步骤：
INT loop_length（名单* N）{
节点*野兔= N *龟= N;
INT相位= 0，CNT = 0;
而（真）{
野兔= hare-＆gt;接着，野兔= hare-＆gt;接着，乌龟= tortoise-＆gt;接着，
如果（野兔==乌龟）相++;
如果（相== 1）CNT ++;
如果（相== 2）回报CNT;
}
}
例如，考虑循环列表
（1） - ＆GT;（2） - ＆GT;（3） - ＆GT;（4）
| |
（6）＆其中 - （5）
该算法的工作原理如下（T =龟，H =野兔）：
/ -------- \
1--2--3--4--5--6阶段CNT
HT 0 0
牛逼小时0 0
牛逼小时0 0
HT 1 1
牛逼H 1 2
H T 1 3
牛逼H 1 4
HT 2 4：终止，CNT = 4
现在是否有形成所述结点用于循环的节点提前X节点（在本例中节点（3）），即X = 2，和循环由Ç节点（在这个例子中C = 4）当龟进入首次结点X后步野兔是在循环在位置（2X - X）％的C，即X（％C）（在这个例子中，龟进入（3）后的2步3ND野兔然后在位置L =（2％4 = 2），即节点（5）（索引从零开始），它现在就（CL-1）步骤野兔到达乌龟（1步骤中的例子）作为野兔具有的L-步骤的'优势;这意味着该算法，直到野兔步骤的数目是否满足龟所述第一时间是
X +（C - X％C - 1）;在实施例2 +（4 - 2 - 1）= 3
C被公知（它计算由算法），和步骤（用S表示）的总数量可以被计算，即，我们有
S + 1 - Visual C = X - X％C
现在假设野兔为q的步骤，即野兔一个额外的好处需要第一Q next指针转发算法开始前;那么当乌龟进入结点野兔是在位置（（X + Q）％C），我们得到
S + 1 - Visual C = X - （X + Q）％C
现在这给出了一个过程来计算从A和B的共同结点P的路径的长度之差（表示长度a和b与它们的差从而AB）（假设A> B不失一般性）。
首先运行启动A点的算法，计算周期的长度C和步骤S_A门店数量。然后运行它，以便乌龟开始于A和野兔在B处并计算步S_X数量。这意味着，野兔具有（AB）的节点，即
现在的优点 S_X + 1 - C = A - （A +（A - B））％C = A - （2A - B）％C
于是
的S - S_X ==（A - B）模ç
即。差别给人的长度差模℃;用C来计算长度差的商从出发点B，得到的步数通常运行算法S_B，即一起
S_A + 1 - C = A - A％C
S_B + 1 - Visual C = B - B％C
S_X - S_A ==（A - B）％C
减去前两个方程得到
S_A - S_B =（A - B）+ -1 *（A％C）+ B％C]
在方括号中的项是] -C，+ C [，所以
（S_A - S_B） - C＆LT; （A - B）＆LT; （S_A - S_B）+ C
在此区间有至多两个区别这等于（S - S_X）模℃;使用这两个试图找出结点---问题就迎刃而解了。
例如：
A（1） - （2）
|
B（3） - （4） - （5） - （6）
\ _________ /
在S_A，经过3个步骤，在（5）和周期长度3兔子和乌龟相遇的计算返回。在S_B，经过3个步骤，在（6）和周期长度3兔子和乌龟相遇的计算返回。对于S_X，野兔在进入B和乌龟在A;后按2步它们满足（4）。这给了
0 - 3版; （A - B）＆LT; 0 + 3
（3 - 2）==（一 - 二）模3
即。之间的长度差（ - b）是1模3;这给了可能的长度差{-2，+ 1}; -2是通过假设A> B忽视，所以我们得到A = B + 1。然后，结点是由从A转发到第一遍历节点1实测值（2），然后从两个臂前进以同样的速度，直到结点被发现。
与那里的非共享环和/或无环作为一个练习的读者的情况下集成。
I was asked this question in some interview.
I was required to write code for finding junction in a linked list (which is in form of Y with both arms not necessarily equal) for production environment in O(1) space and linear time.
I came up with this solution (which i had previously seen somewhere) :
1. Measure lengths of both lists, let them be l1 and l2 2. Move the pointer of larger list by |(l1-l2)|. 3. Now move together both the pointers, if they point to same location, that is the junction.
Interviewer: How will your code handle ?
Case 1. The Y-format linked list has loop in the end after the junction.
Case 2. Either of the input lists is cyclic and they don't merge.
Case 3. The Y-format list has loop in the end before the junction.
In response to case 1, my answer was:
I will find the loop in the list using two pointers (one fast and slow), measure the length to the node at which both the pointers meet and then proceed as previous case.
Whereas, for cases 2 and 3, I was able to figure out no better solution than gracefully exiting when a loop is detected (using the 2-pointer technique).
I believe there are better answers to this problem.Please drop down yours :).
Thanks,
The problem is made difficult by the interviewer's (seeming) interpretation that the following shapes are also considered valid:
A\ _____ A\ ___
\/ \ \ / \
\ / \ \ /
+---' +-------------'
/ P / P
/ /
B/ B/
i.e. there is a junction but then the list loops back to a place either before or after the junction. The procedure of calculating the length of the list does not help directly because the length of a cyclic list is not defined.
First note that the length of a loop at end of a cyclic list can be calculated by this O(1) memory / O(n) time procedure:
int loop_length(List *n) {
Node *hare = n, *tortoise = n;
int phase = 0, cnt = 0;
while (true) {
hare=hare->next; hare=hare->next; tortoise=tortoise->next;
if (hare==tortoise) phase++;
if (phase==1) cnt++;
if (phase==2) return cnt;
}
}
For example, consider the cyclic list
(1)-->(2)-->(3)-->(4)
| |
(6)<--(5)
The algorithm works as follows (T=tortoise, H=hare):
/--------\
1--2--3--4--5--6 phase cnt
HT 0 0
T H 0 0
T H 0 0
HT 1 1
T H 1 2
H T 1 3
T H 1 4
HT 2 4 : TERMINATED, cnt=4
Now if there are X nodes before the node that forms the junction point for the cycle (in the example node (3)), i.e. X=2, and the cycle consists of C nodes (in the example C=4), when the tortoise enters the junction point for the first time after X steps the hare is in the cycle at location (2X - X) % C, i.e. (X % C) (in the example, tortoise enters (3) after 2 steps 3nd hare is then at location L = (2 % 4 = 2), i.e. in node (5) (the index is zero-based). It will now take (C-L-1) steps for the hare to reach the tortoise (1 step in the example) as the hare has an 'advantage' of L steps; this means that the number of steps for the algorithm until the hare meets the tortoise the first time is
X + (C - X % C - 1) ; in the example 2 + (4 - 2 - 1) = 3
C is known (it's calculated by the algorithm), and the total number of steps (denote by S) can be calculated, i.e. we have
S + 1 - C = X - X % C
Suppose now that the hare as an extra advantage of Q steps, i.e. hare takes first Q next pointers forwards before the algorithm starts; then when the tortoise enters the junction point the hare is at location ((X + Q) % C), and we get
S + 1 - C = X - (X + Q) % C
This gives now a procedure to calculate the difference in the length of the paths from 'A' and 'B' to the common junction point P (denote the lengths a and b and their difference thus a-b) (assume a > b without loss of generality).
First run the algorithm from starting point A, calculate cycle length C and store number of steps S_A. Then run it so that the tortoise starts at A and the hare at B and calculate the number of steps S_X. This means that the hare has now an advantage of (a-b) nodes, i.e.
S_X + 1 - C = a - (a + (a - b)) % C = a - (2a - b) % C
Thus
S - S_X == (a - b) modulo C
I.e. the difference gives the length difference modulo C; to calculate the length difference's quotient by C run the algorithm usually from starting point B, getting number of steps S_B, i.e. all together
S_A + 1 - C = a - a % C
S_B + 1 - C = b - b % C
S_X - S_A == (a - b) % C
subtract the first two equations to get
S_A - S_B = (a - b) + [-1 * (a % C) + b % C]
the term in square brackets is in ]-C,+C[ , so
(S_A - S_B) - C < (a - b) < (S_A - S_B) + C
in this interval there are at most two differences which equal (S - S_X) modulo C; use them both to try to spot the junction point---problem solved.
Example:
A(1)--(2)
|
B(3)--(4)--(5)--(6)
\_________/
In the calculation of S_A, the hare and tortoise meet after 3 steps at (5) and cycle length 3 is returned. In the calculation of S_B, the hare and tortoise meet after 3 steps at (6) and cycle length 3 is returned. For S_X, hare enters at B and tortoise at A; they meet after 2 steps at (4). This gives
0 - 3 < (a - b) < 0 + 3
(3 - 2) == (a - b) modulo 3
i.e. the length difference between (a - b) is 1 modulo 3; this gives possible length differences { -2, +1 }; -2 is disregarded by assumption a > b, so we get a = b + 1. Then the junction point is found by traversing first +1 node from A forwards to (2), and then advancing from both arms at the same pace until the junction point is found.
Integration with the cases where there are non-shared loops and/or no loops left as an exercise to the reader.
这篇关于生产code寻找一个链表结的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
