Вопросы на собеседовании по высокочастотному алгоритму: быстрые и медленные указатели

❝

Это первый выпуск публичного аккаунта «Throwable Digest»."24"Оригинальная статья, включенная в альбом "Algorithm Related".

❞

помещение

сегодня(2019-05-10) Во время обеда я просмотрел технический паблик и увидел, что некоторые сеньоры прошлиAntвысотаPВ интервью один из вопросов исследует алгоритм поиска узла в середине односвязного списка. Глядя на алгоритм, я думаю, что решение очень интересное, поэтому я попытаюсь воспроизвести его здесь.

Сцены

Интервьюер: Как получить доступ к промежуточному узлу связанного списка?

Большой парень X: Просто реализуйте, пройдите весь связанный список один раз, затем вычислите длину связанного списка, а затем пройдите второй раз, чтобы найти данные в середине.

Интервьюер: Нужно пройти по связному списку только один раз, так как же это решить?

Большой парень X: Вы можете создать два указателя, один указатель проходит по двум узлам за раз, а другой узел проходит по одному узлу за раз.Когда быстрый указатель проходит к пустому узлу, позиция, на которую указывает медленный указатель, является середина связанного списка, и здесь проблема решается алгоритмом, называемым"Быстрый и медленный указатель".

Обзор

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

Если мы хотим посетить промежуточный узел, окончательный поиск должен бытьn2узел, содержимоеn2.

Если длина односвязного списка является четным числом, которое предполагается равным 4, то:

Если мы хотим посетить промежуточный узел, окончательный поиск должен бытьn2а такжеn3узел, содержимоеn2а такжеn3.

Сначала определите класс узлаNodeследующим образом:

@Data
private static class Node<T> {
    
    /**
     * 当前节点的值
     */
    private T value;

    /**
     * 下一个节点的引用
     */
    private Node<T> next;
}

Мы можем легко построить односвязный список следующим образом:

private static Node<String> buildLinkedList(int len) {
    Node<String> head = new Node<>();
    head.setValue("n1");
    Node<String> tail = head;
    for (int i = 1; i < len; i++) {
        Node<String> node = new Node<>();
        node.setValue("n" + (i + 1));
        tail.setNext(node);
        tail = node;
    }
    return head;
}

Затем мы можем написать метод для поиска промежуточных узлов, сначала написать вычисление длины путем обхода связанного списка, а затем пройти по связанному списку, чтобы получить промежуточный узел."Вариант первый":

    private static List<String> searchByTraversal(Node<String> head) {
        List<String> result = new ArrayList<>(2);
        Node<String> search = head;
        int len = 1;
        // 第一次遍历链表,计算链表长度
        while (search.getNext() != null) {
            search = search.getNext();
            len++;
        }
        int index = 0;
        int mid;
        search = head;
        // 链表长度为偶数
        if ((len & 1) == 0) {
            mid = len / 2 - 1;
            while (search.getNext() != null) {
                if (mid == index) {
                    result.add(search.getValue());
                    result.add(search.getNext().getValue());
                }
                search = search.getNext();
                index++;
            }
        } else {
            mid = (len - 1) / 2;
            while (search.getNext() != null) {
                if (mid == index) {
                    result.add(search.getValue());
                }
                search = search.getNext();
                index++;
            }
        }
        return result;
    }

Напишите основной метод для его проверки:

public static void main(String[] args) throws Exception {
    Node<String> head = buildLinkedList(11);
    System.out.println(searchByTraversal(head));
    head = buildLinkedList(12);
    System.out.println(searchByTraversal(head));
}

// 输出结果
[n6]
[n6, n7]

Предположим, что длина связанного списка равнаn(n > 0), то общее количество элементов, которые необходимо пройти за два обхода, будет следующим:

• Первый обход всего связанного списка, чтобы вычислить длину, должен быть пройденnэлементы.
• Второй нужно пройтиn/2элементы (вnКогда значение относительно велико, на самом деле эффект сложения и вычитания невелик).

При реализации этой схемы итоговая временная сложность будет больше, чемO(n). Следовательно, необходимо рассмотреть схему оптимизации.Ему нужно только один раз пройти по связанному списку, чтобы найти значение узла в середине.Это вторая схема:"Быстрый и медленный указатель".

"Быстрый и медленный указатель", просто чтобы определить два указателя, при переходе по связанному списку быстрый указатель (Fast Pointer) всегда перебирает два элемента, а медленный указатель (Slow Pointer) всегда перебирает элемент. Когда быстрый указатель завершает обход всего связанного списка, медленный указатель просто указывает на средний узел связанного списка. Алгоритм реализуется следующим образом:

/**
 * 基于快慢指针搜索
 */
private static List<String> searchByFastSlowPointer(Node<String> head) {
    List<String> result = new ArrayList<>();
    // fast pointer
    Node<String> fp = head;
    // slow pointer
    Node<String> sp = head;
    int len = 1;
    while (null != fp.getNext()) {
        if (fp.getNext().getNext() != null) {
            fp = fp.getNext().getNext();
            sp = sp.getNext();
            len += 2;
        } else {
            fp = fp.getNext();
            len += 1;
        }
    }
    // 链表长度为偶数
    if ((len & 1) == 0) {
        result.add(sp.getValue());
        result.add(sp.getNext().getValue());
    } else {
        result.add(sp.getValue());
    }
    return result;
}

Напишите основной метод для его проверки:

public static void main(String[] args) throws Exception {
    Node<String> head = buildLinkedList(11);
    System.out.println(searchByFastSlowPointer(head));
    head = buildLinkedList(12);
    System.out.println(searchByFastSlowPointer(head));
}

// 输出结果
[n6]
[n6, n7]    

Из-за использования схемы быстрого и медленного указателя выполняется только один обход связанного списка, а поскольку быстрый указатель проходит по двум элементам за раз, итоговая временная сложность меньше, чемO(n).

Сценарии применения быстрых и медленных указателей

Быстрые и медленные указатели в основном имеют следующие сценарии применения:

1. Найдите середину связанного списка.
2. Проверьте, есть ли цикл в связанном списке.
3. удалить предпоследний в связанном спискеxузел.

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

Проверить, есть ли цикл в связанном списке

Предположим, что связанный список имеет 6 узлов (головной узел — n1, хвостовой узел — n6), и кольцо образовано (следующим узлом из n6 является n1):

При использовании быстрых и медленных указателей быстрый указатель будет проходить на один элемент больше, чем медленный. быстрый указатель всегда может догнать медленный указатель (быстрый указатель и медленный указатель указывают на один и тот же узел), в это время можно судить, что связанный список сформировал кольцо; в противном случае быстрый указатель выскочит цикла после одного обхода, и он никогда не «совпадет» с медленным указателем. Грубая реализация выглядит следующим образом:

// 判断链表是否存在环
private static boolean cyclic(Node<String> head) {
    // fast pointer
    Node<String> fp = head;
    // slow pointer
    Node<String> sp = head;
    while (fp.getNext() != null) {
        fp = fp.getNext().getNext();
        sp = sp.getNext();
        if (sp.equals(fp)) {
            return true;
        }
    }
    return false;
}

// 生成环形链表
private static Node<String> buildCyclicLinkedList(int len) {
    Node<String> head = new Node<>();
    head.setValue("n1");
    Node<String> tail = head;
    for (int i = 1; i < len; i++) {
        Node<String> node = new Node<>();
        node.setValue("n" + (i + 1));
        tail.setNext(node);
        tail = node;
    }
    tail.setNext(head);
    return head;
}

есть тест:

public static void main(String[] args) throws Exception {
    Node<String> head = buildCyclicLinkedList(11);
    System.out.println(cyclic(head));
    head = buildLinkedList(11);
    System.out.println(cyclic(head));
}

// 输出结果
true
false

Удалить N-й последний узел в связанном списке

этоLeetCodeВышеупомянутая проблема алгоритма, в которой используется метод добавления виртуального головного узла и быстрого и медленного указателя, может быть решена только одним обходом. Вот цитата из самого проголосовавшего ответа:

❝

Приведенный выше алгоритм можно оптимизировать для использования только одного прохода. Мы можем использовать два указателя вместо одного. Первый указатель перемещается вперед на n+1 шагов от начала списка, а второй указатель начинается с начала списка. Теперь два указателя разделены n узлами. Мы поддерживаем этот постоянный интервал, одновременно перемещая оба указателя вперед, пока первый указатель не достигнет последнего узла. В этот момент второй указатель будет указывать на n-й узел от последнего узла. Мы повторно связываем следующий указатель узла, на который ссылается второй указатель, чтобы он указывал на следующий узел узла.

❞

Схема вывода алгоритма:

Код алгоритма выглядит следующим образом:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

Временная сложностьO(L),Lдлина связанного списка.

резюме

Учитывая, что алгоритм относительно слаб, стоит выводить и учиться видеть эти относительно практические проблемы и решения.

Использованная литература:

• Leetcode, Тема алгоритма: Удалить N-й узел из конца списка

(Конец этой статьи c-2-d e-a-20190510 r-a-20200717 Изображение на обложке взято из «Sword Art Online»)