Медленный бегун в конце концов встретится с быстрым бегуном на круговой дорожке…

В первый раз, когда я увидел 142. Linked List Cycle II, я ставлю лишнее значение visited в каждый из узлов, чего нельзя допускать и это также занимает больше памяти.

Лучшим решением является использование двух указателей, которые я хотел бы назвать «два бегуна», потому что это помогает мне представить это в моей голове. Представьте, что есть два бегуна, и если они продолжат бежать по круговой дорожке, то в какой-то момент встретятся. Если дорожка не круглая, они никогда не смогут встретиться друг с другом.

С учетом этого 141. Linked List Cycle было бы очень просто.

141. Цикл связанного списка

Учитывая связанный список, определите, есть ли в нем цикл.

Чтобы представить цикл в данном связанном списке, мы используем целое число pos, которое представляет позицию (с индексом 0) в связанном списке, к которой соединяется хвост. Если pos равно -1, то в связанном списке нет цикла.

var hasCycle = function(head) {
    if(!head || !head.next || !head.next.next) return false;
    let fast = head.next.next;
    let slow = head.next;
    
    while(fast !== slow){
        if(!fast.next || !fast.next.next) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

Нам просто нужно настроить указатель fast и slow и посмотреть, могут ли они быть равными в какой-то момент. Есть мелкие вещи, требующие внимания.

  1. нам нужно проверить первые 3 узла, прежде чем двигаться дальше.
  2. мы не можем установить fast и slow в head в качестве начальных значений, потому что они никогда не попадут в цикл.
  3. в цикле нам нужно проверить еще 2 узла на fast .

142. Цикл связанного списка II

Учитывая связанный список, верните узел, с которого начинается цикл. Если цикла нет, вернуть null.

Чтобы представить цикл в данном связанном списке, мы используем целое число pos, которое представляет позицию (с индексом 0) в связанном списке, к которой соединяется хвост. Если pos равно -1, то в связанном списке нет цикла.

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

Обратите внимание, что fast и slow встречаются в любых узлах цикла, откуда мы знаем, где он начинается?

Когда fast и slow встречаются в P , мы знаем, что fast пробежал m круг, а slow пробежал n круга.

fDis = a + (b+c)*m + b
sDis = a + (b+c)*n + b

Поскольку fast работает в два раза быстрее, чем slow, fDis = 2 *sDis.

И мы также знаем, что P = a + b и R = a .

Таким образом, мы можем легко получить a + b = (b+c)(m-2n) , что означает, что если бегун пробежит a + b , другой бегун пробежит несколько кругов. Итак, если мы поместим один указатель p1 в новичок, а другой указатель p2 в P (где встретились fast и slow), p1 и p2 встретятся в R (где начинается цикл).

var detectCycle = function(head) {
    if(!head || !head.next || !head.next.next) return null;
    let fast = head.next.next;
    let slow = head.next;
    while(fast !== slow){
        if(!fast.next || !fast.next.next) return null;
        fast = fast.next.next;
        slow = slow.next;
    }
    let p1 = fast;
    let p2 = head;
    while(p1 !== p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
};

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

  1. Приходится устанавливать первые шаги как для fast, так и для slow. Я установил только fast и сделал slow = head, что не работает, потому что fDis !== 2 * sDis .
  2. Не забывайте проверять fast.next при проверке fast.next.next.

Развлекайся!