用于在链表中查找结点的生产代码 [英] Production code for finding junction in a linked list
问题描述
我在一些采访中被问到这个问题.
I was asked this question in some interview.
我被要求在 O(1) 空间和线性时间的生产环境中编写用于在链表(Y 形式，双臂不一定相等)中查找结点的代码.
我想出了这个解决方案(我以前在某处见过):
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. Y 格式的链表在结点之后最后有循环.
情况 2. 任何一个输入列表都是循环的，它们不会合并.
情况 3. Y 格式的列表在结点前最后有循环.
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.
针对情况 1，我的回答是:
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.
然而，对于案例 2 和 3，我想不出比在检测到循环时优雅退出更好的解决方案(使用 2 指针技术).
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 :).
谢谢，
推荐答案
由于面试官的(表面上的)解释，以下形状也被认为是有效的，问题变得很困难:
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.
首先注意循环列表末尾的循环长度可以通过这个O(1)内存/O(n)时间过程计算:
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;
}
}
例如，考虑循环列表
(1)-->(2)-->(3)-->(4)
| |
(6)<--(5)
算法的工作原理如下(T=乌龟，H=野兔):
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
现在如果在形成循环的结点的节点之前有X个节点(在示例节点(3)中)，即X=2，并且循环由C个节点组成(在示例中C=4), 当乌龟在 X 步后第一次进入结点时，兔子在循环中的位置 (2X - X) % C，即 (X % C)(在示例中，乌龟在 2 步后进入(3)然后第三只兔子在位置 L = (2 % 4 = 2)，即在节点 (5)(索引从零开始).现在兔子需要 (CL-1) 步才能到达乌龟 (1)示例中的步骤)，因为兔子有 L 步的优势"；这意味着算法的步骤数直到兔子第一次遇到乌龟是
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 是已知的(由算法计算出来的)，可以计算出总步数(用 S 表示)，即我们有
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
现在假设野兔作为 Q 步的额外优势，即野兔在算法开始之前先向前 Q 个 next 指针；然后当乌龟进入连接点时，兔子在位置 ((X + Q) % 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
现在给出了计算从A"和B"到公共连接点 P 的路径长度差异的程序(表示长度 a 和 b 以及它们的差异 ab)(假设 a > b不失一般性).
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).
首先从起点A运行算法，计算循环长度C并存储步数S_A.然后运行它，让乌龟从 A 开始，兔子从 B 开始，并计算步数 S_X.这意味着野兔现在拥有 (a-b) 个节点的优势，即
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
因此
S - S_X == (a - b) modulo C
即差值给出模 C 的长度差值；要通过 C 计算长度差的商，通常从起点 B 运行算法，获得步数 S_B，即全部在一起
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
将前两个方程相减得到
S_A - S_B = (a - b) + [-1 * (a % C) + b % C]
方括号中的术语在 ]-C,+C[ 中，所以
the term in square brackets is in ]-C,+C[ , so
(S_A - S_B) - C < (a - b) < (S_A - S_B) + C
在这个区间内最多有两个差值等于 (S - S_X) 模 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.
示例:
A(1)--(2)
|
B(3)--(4)--(5)--(6)
\_________/
在S_A的计算中，兔子和乌龟在(5)处3步后相遇，返回循环长度3.在 S_B 的计算中，兔子和乌龟在 (6) 处经过 3 步后相遇，返回循环长度 3.对于S_X，兔子从B进入，乌龟从A进入；他们在 (4) 的 2 步后相遇.这给
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
即(a - b) 之间的长度差为 1 模 3；这给出了可能的长度差异 { -2, +1 };-2 被假设 a > b 忽略，所以我们得到 a = b + 1.然后通过从 A 向前遍历第一个 +1 节点到(2)，然后以相同的速度从双臂前进直到找到连接点找到连接点.
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.
这篇关于用于在链表中查找结点的生产代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
