Алгоритм для поиска в односвязном списке k-го элемента с конца

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

При решение данной задачи помните, что можно выбрать значение k так, что при передаче k = 1 мы получим последний элемент, 2 – предпоследний и т.д. Или выбрать k так, чтобы k = 0 соответствовало последнему элементу.

Решение 1. Размер связного списка известен

Если размер связного списка известен, k-й элемент с конца легко вычислить (длина – k). Нужно пройтись по списку и найти этот элемент.

Решение 2. Рекурсивное решение

Такой алгоритм рекурсивно проходит связный список. По достижении последнего элемента алгоритм начинает обратный отсчет, и счетчик сбрасывается в 0. Каждый шаг инкрементирует счетчик на 1. Когда счетчик достигнет k, искомый элемент будет найден.

Реализация этого алгоритма коротка и проста – достаточно передать назад целое значение через стек. К сожалению, оператор return не может вернуть значение узла. Так как же обойти эту трудность?

Подход А: не возвращайте элемент

Можно не возвращать элемент, достаточно вывести его сразу, как только он будет найден. А в операторе return вернуть значение счетчика.

public static int nthToLast(LinkedListNode head, int k) {
    if (head == null) {
        return 0;
    }
    int i = nthToLast(head.next, k) + 1;
    if (i == k) {
        System.out.println(head.data);
    }
    return i;
}

Решение верно, но можно пойти другим путем.

Подход Б: используйте C++

Второй способ – использование С++ и передача значения по ссылке. Такой подход позволяет не только вернуть значение узла, но и обновить счетчик путем передачи указателя на него.

node* nthToLast(node* head, int k, int& i) {
    if (head == NULL) {
        return NULL;
    }
    node* nd = nthToLast(head->next, k, i);
    i = i + 1;
    if (i == k) {
        return head;
    }
    return nd;
}

Решение 3. Итерационное решение

Итерационное решение будет более сложным, но и более оптимальным. Можно использовать два указателя – p1 и p2. Сначала оба указателя указывают на начало списка. Затем перемещаем p2 на k узлов вперед. Теперь мы начинаем перемещать оба указателя одновременно. Когда p2 дойдет до конца списка, p1 будет указывать на нужный нам элемент.

LinkedListNode nthToLast(LinkedListNode head, int k) {
    if (k <= 0) return 0;

    LinkedListNode p1 = head;
    LinkedListNode p2 = head;
    
    for (int i = 0; i < k - 1; i++) {
        if (p2 == null) return null;
            p2 = p2.next;
    }
    if (p2 == null) return null;
    
    while (p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

_{Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».}

Как Яндекс использует ваши данные и машинное обучение для персонализации сервисов — читать и смотреть YaC 2019.