Код продукта для поиска соединения в связанном списке

Question

Мне задали этот вопрос в каком-то интервью.

Мне потребовалось написать код для нахождения соединения в связанном списке (который находится в форме Y с обеими руками, не обязательно равными) для производственной среды в пространстве O (1) и линейном времени.
Я придумал это решение (которое я раньше видел где-то):

 
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 я не смог найти лучшего решения, чем изящно выходить, когда обнаружен цикл (используя технику с двумя указателями).

Я считаю, что есть более эффективные ответы на эту проблему. Пожалуйста, опустите свой :).

Спасибо,

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) 

алгоритм работает следующим образом (Т = черепаха, Н = заяц):

 /--------\ 
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) (в примере черепаха входит (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 

С известно (он вычисляется по алгоритму), а общее число шагов (обозначит через S) может рассчитываться, т.е.мы имеем

S + 1 - C = X - X % C 

Предположим теперь, что заяц как дополнительное преимущество Q шагов, т.е. зайцем занимает первое Q следующие указатели вперед до начала алгоритма; Затем, когда черепаха попадает в точку соединения зайца находится в положении ((Х + Q),% С), и мы получаем

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

Это дает теперь процедуру для вычисления разницы в длине пути от ' A 'и' B 'к общей точке соединения P (обозначим длины a и b и их разность, таким образом, ab) (предположим a> b без потери общности).

Сначала запустите алгоритм из начальной точки A, вычислите длину цикла C и сохраните количество шагов S_A. Затем запустите его так, чтобы черепаха начиналась с A и заяц на B и вычисляла количество шагов S_X. Это означает, что заяц теперь имеет преимущество (а-б) узлы, т.е.

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] 

термина в квадратные скобки в] -С, + с [, так что

(S_A - S_B) - C < (a - b) < (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; они встречаются после двух шагов (4). Это дает

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), а затем перехода от обоих рук в том же темпе до тех пор, пока точка соединения найдена.

Интеграция с случаями, когда в считывающее устройство оставлены не общие петли и/или отсутствуют петли.