Найти i-й элемент с конца LinkedList за один проход

Найти i-й элемент с конца LinkedList за один проход

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

Подход: Two Pointers (Два указателя)

Идея в том, что мы используем медленный и быстрый указатели с расстоянием в i элементов между ними.

Алгоритм:

1. Создаем два указателя: первый и второй
2. Перемещаем второй указатель на i позиций вперед
3. Затем перемещаем оба указателя вместе, пока второй не достигнет конца
4. Когда второй указатель на конце, первый указатель находится на позиции i от конца

Полное решение с обработкой ошибок

public class LinkedListKthFromEnd {
    // Определение узла LinkedList
    static class Node {
        int value;
        Node next;
        
        Node(int value) {
            this.value = value;
        }
    }
    
    /**
     * Найти i-й элемент с конца списка за один проход
     * Время: O(n)
     * Пространство: O(1)
     */
    public static Node findKthFromEnd(Node head, int k) {
        // Обработка пустого списка
        if (head == null) {
            throw new IllegalArgumentException("Список пуст");
        }
        
        Node first = head;   // указатель для отсчета k позиций
        Node second = head;  // указатель, который пойдет в конец
        
        // Перемещаем first указатель на k позиций вперед
        for (int i = 0; i < k; i++) {
            // Если k больше длины списка, возвращаем null или выбрасываем исключение
            if (first == null) {
                throw new IllegalArgumentException("k больше длины списка");
            }
            first = first.next;
        }
        
        // Теперь перемещаем оба указателя, пока first не станет null
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        return second;  // second находится на позиции k от конца
    }
    
    public static void main(String[] args) {
        // Создание списка: 1 -> 2 -> 3 -> 4 -> 5
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        
        // Тестирование
        try {
            Node result1 = findKthFromEnd(head, 1);
            System.out.println("1-й с конца: " + result1.value);  // 5
            
            Node result2 = findKthFromEnd(head, 2);
            System.out.println("2-й с конца: " + result2.value);  // 4
            
            Node result5 = findKthFromEnd(head, 5);
            System.out.println("5-й с конца: " + result5.value);  // 1
            
            // Обработка ошибки
            Node result6 = findKthFromEnd(head, 6);  // выбросит исключение
        } catch (IllegalArgumentException e) {
            System.out.println("Ошибка: " + e.getMessage());
        }
    }
}

Визуализация работы алгоритма

Список: [1, 2, 3, 4, 5], найти 2-й с конца

Шаг 1: Перемещаем first на k=2 позиции
first: 3 -> 4 -> 5
second: 1 -> 2 -> 3 -> 4 -> 5

Шаг 2: Перемещаем оба указателя
first: 4 -> 5
second: 2 -> 3 -> 4 -> 5

Шаг 3: Перемещаем оба указателя
first: 5
second: 3 -> 4 -> 5

Шаг 4: Перемещаем оба указателя
first: null
second: 4 -> 5  <- это наш ответ

Альтернативное решение с функцией поиска

public class LinkedListKthFromEndV2 {
    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }
    
    /**
     * Альтернативный подход: проверяем, что k валидна
     */
    public static Node findKthFromEnd(Node head, int k) {
        // Валидация
        if (head == null || k <= 0) {
            return null;
        }
        
        Node fast = head;
        Node slow = head;
        
        // Перемещаем fast на k шагов
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return null;  // k больше длины списка
            }
            fast = fast.next;
        }
        
        // Если fast стал null сразу, значит k == длине списка
        if (fast == null) {
            return head;  // возвращаем первый элемент
        }
        
        // Перемещаем оба указателя
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

Еще один вариант: вернуть значение вместо узла

public class LinkedListKthValue {
    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }
    
    /**
     * Возвращает значение i-го элемента с конца
     */
    public static Integer findKthValueFromEnd(Node head, int k) {
        Node node = findKthNodeFromEnd(head, k);
        return node != null ? node.value : null;
    }
    
    private static Node findKthNodeFromEnd(Node head, int k) {
        if (head == null || k <= 0) return null;
        
        Node first = head;
        Node second = head;
        
        for (int i = 0; i < k; i++) {
            if (first == null) return null;
            first = first.next;
        }
        
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        return second;
    }
}

Анализ сложности

• Временная сложность: O(n) — проходим по списку один раз
• Пространственная сложность: O(1) — используем только два дополнительных указателя

Это оптимально, так как мы не можем найти элемент с конца быстрее, чем за один проход.

Граничные случаи

1. Пустой список — возвращаем null или выбрасываем исключение
2. k = 1 — последний элемент
3. k = длина списка — первый элемент
4. k > длина списка — невозможно найти, возвращаем null
5. k <= 0 — невалидный параметр

На что обратить внимание на собеседовании

1. Спросите граничные случаи перед написанием кода
2. Объясните подход перед кодированием
3. Проверьте свое решение на примерах
4. Обсудите альтернативы (например, рекурсивный подход, но он требует O(n) память)
5. Подчеркните оптимальность — O(n) время и O(1) место это лучшее что можно сделать