Интервью: Remove Loop в связанном списке - Java

Ответ 1

Эта проблема состоит из двух частей:

• Обнаружение, если в списке есть цикл
• Определите начало цикла

Как только вы знаете, где начинается цикл, легко идентифицировать последний элемент в списке, так как он является элементом в списке после начала цикла, который заканчивается, указывая на начало цикла. Затем тривиально установить следующий указатель/ссылку этого элемента на null, чтобы исправить список циклических ссылок (а не круговой связанный список, в котором последние элементы указывают на первый), это будет конкретный экземпляр циклических списков).

• Алгоритм обнаружения цикла Floyd, также называемый алгоритмом черепахи и зайца, поскольку он включает использование двух указателей/ссылок, которые перемещаются на разных скорости, является одним из способов обнаружения цикла. Если есть цикл, два указателя (например, p1 и p2) в конечном итоге указывают на один и тот же элемент после конечного числа шагов. Интересно, что можно доказать, что элемент, с которым они встречаются, будет тем же самым расстоянием до начала цикла (продолжая перемещаться по списку в том же направлении вперед) в качестве начала цикла относится к голове списка. То есть, если в линейной части списка есть элементы k, два указателя будут встречаться внутри цикла длиной m в точке m-k от начала цикла или элемента k до конца 'цикла (конечно, это цикл, так что он не имеет "конца" - это просто "начало" еще раз). И это дает нам возможность найти начало цикла:

• Как только цикл был обнаружен, пусть p2 останется указывать на элемент, в котором цикл для вышеописанного шага, но reset p1, чтобы он возвращался к заголовку списка. Теперь переместите каждый указатель на один элемент за раз. Поскольку p2 начинается внутри цикла, он будет продолжать цикл. После k шагов (равных расстоянию начала цикла от головки списка), p1 и p2 снова соберутся. Это даст вам ссылку на начало цикла.

• Теперь легко установить p1 (или p2), чтобы указать на элемент, начинающий цикл, и пройти цикл до тех пор, пока p1 не вернется к исходному элементу. На данный момент p1 ссылается на "последний" список элементов, а следующий указатель может быть установлен на null.

Вот некоторый быстрый и грязный Java-код, предполагающий связанный список Node, где a Node имеет ссылку next. Это может быть оптимизировано, но оно должно дать вам основную идею:

Node slow, fast, start;
fast = slow = head;

//PART I - Detect if a loop exists
while (true)
{
    // fast will always fall off the end of the list if it is linear
    if (fast == null || fast.next == null)
    {
        // no loop
        return;
    }
    else if (fast == slow || fast.next == slow)
    {
        // detected a loop
        break;
    }
    else
    {
        fast = fast.next.next; // move 2 nodes at at time
        slow = slow.next; // move 1 node at a time
    }
}

//PART II - Identify the node that is the start of the loop
fast = head; //reset one of the references to head of list

//until both the references are one short of the common element which is the start of the loop
while(fast.next != slow.next) 
{
    fast = fast.next;
    slow = slow.next;
}

start = fast.next;

//PART III - Eliminate the loop by setting the 'next' pointer 
//of the last element to null
fast = start;
while(fast.next != start)
{
    fast = fast.next;
}

fast.next = null; //break the loop

Это объяснение может помочь, почему Part II:

Предположим, что длина цикла равна M, и длина остальной части связанный список - L. Дайте понять какова позиция в цикле, когда t1/t2 сначала встречаются?

Определить первый node в цикле позиции 0, следуя ссылкам, мы имеют положение 1, 2,..., до М-1. ( когда мы ходим в цикле, наш текущий position (walk_length) mod M, правильно?) Пусть t1/t2 сначала встречается в позиции p, то время их прохождения (L + k1 * M + p)/v = (L + k2 * M + p)/2v для некоторого k1

Итак, заключает, что если t1 начинается с p, t2 начинать с головы и перемещаться по с той же скоростью, то грантополучатель встретится в позиции 0, первый nodeцикл. Что и требовалось доказать.

Дополнительные ссылки:

• http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
• Объясните, как работает запуск цикла node в связанном циклическом списке?
• Доказательство обнаружения начала цикла в связанном списке
• Христо ответил на этот вопрос на этой странице также цитирует объяснение из книги интервью

Ответ 2

Решение 1 - любезно предоставлено Карьерным кубком и книгой "Cracking the Coding Interview" :

public static LinkedListNode findStartOfLoop(LinkedListNode head) {
    LinkedListNode n1 = head;
    LinkedListNode n2 = head; 

    // find meeting point using Tortoise and Hare algorithm
    // this is just Floyd cycle detection algorithm
    while (n2.next != null) { 
        n1 = n1.next; 
        n2 = n2.next.next; 
        if (n1 == n2) { 
            break; 
        }
    }

    // Error check - there is no meeting point, and therefore no loop
    if (n2.next == null) {
        return null;
    }

    /* Move n1 to Head. Keep n2 at Meeting Point.  Each are k steps
    /* from the Loop Start. If they move at the same pace, they must
     * meet at Loop Start. */
    n1 = head; 
    while (n1 != n2) { 
        n1 = n1.next; 
        n2 = n2.next; 
    }
    // Now n2 points to the start of the loop.
    return n2;
}

Объяснение этого решения прямо из книги:

Если мы переместим два указателя, один с скорость 1 и другая со скоростью 2, они закончит встречу, если связанный список имеет цикл. Зачем? Подумайте о двух автомобили, движущиеся по трассе; более быстрый автомобиль всегда будет проходить медленнее!

Трудная часть здесь - поиск начала цикла. Представьте себе, как аналог, два человека, мчащиеся по трассе, один работает в два раза быстрее, чем Другие. Если они начнут с того же место, когда они последуют в следующий раз? Oни будут встречаться в начале следующий круг.

Теперь давайте предположим, что у Fast Runner был начальный уровень k метров n шаг. Когда они последуют встретить? Они будут встречаться k метров до начало следующего круга. (Почему? Бегун сделал бы k + 2 (n - k) шаги, включая его начало, и Медленный бегун сделал бы n - k шаги. Оба будут к шагам до начало цикла).

Теперь, возвращаясь к проблеме, когда Fast Runner (n2) и Slow Runner (n1) перемещается по нашей круговой связанный список, n2 будет иметь запуск головки на петле, когда n1 входит. В частности, он будет иметь начальное начало k, где k - число узлов перед циклом. Так как n2 имеет начальный запуск k узлов, n1 и n2 будет соответствовать к узлам до начала цикл.

Итак, теперь мы знаем следующее:

• Глава - это k узлов из LoopStart (по определению)
• MeetingPoint для n1 и n2 - это k узлов из LoopStart (как показано выше)

Таким образом, если мы переместим n1 обратно в Head и сохраним n2 в MeetingPoint и переместим их оба в том же темпе, они будут встречаться в LoopStart

Решение 2 - любезно предоставлено мной:)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexer = 0;
    Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
    map.put(head, indexer);
    indexer++;

    // start walking along the list while putting each node in the HashMap
    // if we come to a node that is already in the list, 
    // then that node is the start of the cycle 
    LinkedListNode curr = head;
    while (curr != null) {

        if (map.containsKey(curr.next)) {
            curr = curr.next;
            break;
        }
        curr = curr.next;
        map.put(curr, indexer);
        indexer++;
    }
    return curr;
}

Надеюсь, это поможет. Христо

Ответ 3

Этот ответ не предназначен для конкуренции за ответ, а скорее для того, чтобы объяснить немного больше о встрече двух узлов в черепахе и алгоритме зайца.

• Оба узла в конечном итоге войдут в цикл. Поскольку один движется быстрее (F), чем другой (S), (F), в конце концов, будет скошен (S).

• Если начало цикла находится в заголовке списка, (F) должно встретить (S) назад в заголовке списка. Это ТОЛЬКО, потому что (F) скорость 2X (S); если бы это было 3X, это было бы неверно. Это верно, потому что (F) завершает один круг, когда (S) завершает половину круга, поэтому, когда (S) завершает свой первый круг, (F) завершает два круга - и возвращается в начале цикла с (S).

• Если начало цикла не находится в заголовке списка, то к моменту (S), входящему в цикл, (F) имеет начальное начало (k) узлов в цикле. Поскольку (S) скорость составляет только один node за раз, она будет встречаться (F) в (k) узлах от начала цикла - как в, (k) больше шагов до достижения начала, NOT (k) шагов ПОСЛЕ начало. Это было бы неверно, если бы (S) скорость не была одной, а соотношение скоростей не было 2: 1 между (F) и (S).

  3,1. Вот где это становится немного сложно объяснить. Мы можем согласиться с тем, что (F) продолжит притирание (S) до тех пор, пока они не сойдутся (см. 1 выше), но почему в (k) узлах от начала цикла? Рассмотрим следующее уравнение, где M - количество узлов или расстояние от цикла, а k - начало головки (F); уравнение представляет собой расстояние, пройденное (F) заданным временем t слева в терминах расстояния, пройденного справа (S):

  d_F (t) = 2 * d_S (t) + k

  Итак, когда (S) входит в цикл и пробегает 0 дистанции в цикле, (F) пробегает только расстояние (k). К моменту времени d_S = M - k, d_F = 2M - k. Поскольку мы также должны использовать модульную математику с учетом того, что M представляет собой полное расстояние одного круга в цикле, ПОЗИЦИЯ (F) и (S) в любом целом M (без остатка) равна 0. Итак, тогда в терминах POSITION (или дифференциал), это оставляет k (вернее, -k).

  Итак, наконец, (S) и (F) будут встречаться в позиции (0 - k) или (k) узлах от начала цикла.

• В соответствии с [3] выше, поскольку (k) представляет начальный старт (F), и когда (F) прошел 2X, расстояние (S) перемещалось, чтобы войти в петлю из головки списка, (k) также представляет собой расстояние от начала списка, которое затем представляет начало цикла.

Это немного поздно, поэтому я надеюсь, что я четко сформулировал это. Сообщите мне об этом, и я попытаюсь обновить свой ответ.

Ответ 4

Если использовать хэш-карту идентификации (например, IdentityHashMap), это очень легко решить. Однако он использует больше места.

Переместите список узлов. Для каждого встреченного node добавьте его в идентификационную карту. Если node уже существует в идентификационной карте, то список имеет круговую ссылку и известен node, который был до этого конфликта (либо проверить перед перемещением, либо сохранить "последний node" ) - просто установите "next", если это необходимо, чтобы разорвать цикл.

После этого простого подхода должно быть веселое упражнение: код остается как упражнение для читателя.

Счастливое кодирование.

Ответ 5

 0--->1---->2---->3---->4---->5---->6
                  ▲                 |
                  |                 ▼
                 11<—-22<—-12<—-9<—-8  

Вставьте фиктивный элемент node после каждого node списка ссылок и перед установкой проверьте, что node рядом со следующим является фиктивным или нет. Если рядом со следующим является фиктивный, вставьте нуль в следующий из этого node.

 0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6
                     ▲                      |
                  /                         ▼
                 11<—D<-22<—D<-12<—D<-9<—D<--8 


Node(11)->next->next == D
Node(11)->next =null