代码之家 › 专栏 › 技术社区 › sud03r

用于在链接列表中查找连接的生产代码

linked-list algorithm c c++

sud03r · 技术社区 · 15 年前

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

在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.

采访者:你的代码将如何处理?

案例1。Y格式的链接列表在连接后的末尾有循环。
案例2。任何一个输入列表都是循环的,它们不会合并。
案例3。Y格式列表在连接前的末尾有循环。

作为对案例1的回应,我的回答是:

我将使用两个指针(一个快速指针和一个慢速指针)在列表中找到循环,测量两个指针相遇的节点的长度,然后按照前面的情况继续。

然而,对于第2和第3种情况,在检测到循环时(使用2指针技术),没有比优雅地退出更好的解决方案了。

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

谢谢,

1 回复 | 直到 15 年前

Antti Huima 15 年前

面试官(似乎)认为以下形状也被认为是有效的,这使问题变得困难:

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=乌龟,h=兔子):

       /--------\
 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)(在示例中,乌龟enteRS(3)经过2个步骤后,第3个兔子在位置L=(2%4=2),即在节点(5)中(索引为零)。现在,兔子到达乌龟(示例中的1步)将采取(c-l-1)步,因为兔子具有l步的“优势”;这意味着算法的步数直到兔子第一次遇到乌龟为止是

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

c是已知的(由算法计算),并且可以计算总步数(用s表示),即

  S + 1 - C = X - X % C

假设现在兔子作为q步进的一个额外优势,即兔子在算法开始前向前移动第一个q下一个指针;然后当乌龟进入连接点时兔子在位置((x+q)%c),我们得到

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

这给出了一个计算从“A”和“B”到公共连接点P的路径长度差异的程序(表示长度A和B及其差异,因此A-B)(假设A>B不失一般性)。

首先从起点A开始运行算法,计算循环长度C并存储步骤数s_a,然后运行它,使乌龟从a开始,然后 野兔在 并计算步骤数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]

方括号中的术语是in]-c,+c[,so

  (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&U,兔子在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。然后,将第一个+1节点从A向前移动到(2),然后以相同的速度从双臂向前移动,直到找到连接点。

与存在非共享循环和/或没有循环的情况集成,作为读者的练习。