c++ - 用于在链表中查找连接点的生产代码

Question

我在一些采访中被问到这个问题。

我被要求为 O(1) 空间和线性时间的生产环境编写代码以在链表(以 Y 的形式，双臂不一定相等)中查找连接点。
我想出了这个解决方案(我以前在某处看到过):

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.

面试官:你的代码将如何处理？

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，我的回答是:

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 指针技术)更好的解决方案。

我相信这个问题有更好的答案。请放下你的:)。

谢谢，

Answer 1

面试官(看似)认为以下形状也被认为有效的解释使问题变得困难:

A\  _____     A\              ___
  \/     \      \            /   \
   \     /       \           \   /
    +---'         +-------------'
   / P           / P
  /             /
B/            B/

即有一个路口，但列表会循环回到路口之前或之后的某个地方。计算链表长度的过程并没有直接帮助，因为循环链表的长度没有定义。

首先请注意，循环列表末尾的循环长度可以通过此 O(1) 内存/O(n) 时间过程计算:

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=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)然后第 3 只兔子位于位置 L = (2 % 4 = 2)，即在节点 (5) 中(索引从零开始)。现在兔子需要 (C-L-1) 步才能到达乌龟 (1示例中的步骤)因为兔子有 L 步的“优势”；这意味着在兔子第一次遇到乌龟之前算法的步骤数是

  X + (C - X % C - 1)     ; in the example 2 + (4 - 2 - 1) = 3

C已知(由算法计算)，总步数(记为S)可以计算，即我们有

  S + 1 - C = X - X % C

现在假设野兔作为 Q 步的额外优势，即在算法开始之前，野兔将 first Q next 指针向前；然后当乌龟进入连接点时，兔子在位置 ((X + Q) % C)，我们得到

  S + 1 - C = X - (X + Q) % C

现在给出了一个程序来计算从“A”和“B”到公共(public)连接点 P 的路径长度差(表示长度 a 和 b 以及它们的差 a-b)(假设 a > b不失一般性)。

首先从起点A开始运行算法，计算循环长度C并存储步数S_A。然后运行它，使乌龟从 A 开始，兔子从 B 开始，并计算步数 S_X。这意味着野兔现在拥有 (a-b) 个节点的优势，即

  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，即全部在一起

  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[中，所以

  (S_A - S_B) - C < (a - b) < (S_A - S_B) + C

在这个区间内最多有两个差值等于(S - S_X)模C；使用它们来尝试发现连接点——问题已解决。

例子:

 A(1)--(2)
        |
 B(3)--(4)--(5)--(6)
        \_________/

在 S_A 的计算中，兔子和乌龟在(5)处经过 3 步后相遇，返回循环长度 3。在S_B的计算中，兔子和乌龟在(6)处经过3步后相遇，返回循环长度3。对于S_X，兔子在B处进入，乌龟在A处进入；他们在 (4) 的 2 步后相遇。这给出了

  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)，然后从双臂以相同的速度前进直到找到了连接点。

结合存在非共享循环和/或没有循环的情况作为练习留给读者。