Как найти пятый элемент с конца в связанном списке?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

Связанный список — это структура данных, состоящая из узлов, где каждый узел содержит данные и ссылку на следующий узел. В отличие от массивов, связанные списки не предоставляют прямого доступа к элементам по индексу, что делает задачи, такие как нахождение элемента с конца, более сложными.

Чтобы найти пятый элемент с конца в связанном списке, можно использовать метод с двумя указателями. Этот метод эффективен и не требует дополнительной памяти.

Пошаговое объяснение

1. Инициализация указателей: Создаем два указателя, first и second, которые изначально указывают на голову списка.

2. Перемещение первого указателя: Двигаем first на пять узлов вперед. Это создаст разрыв в пять узлов между first и second.

3. Совместное перемещение указателей: Перемещаем оба указателя одновременно, пока first не достигнет конца списка. Когда first окажется на последнем элементе, second будет указывать на пятый элемент с конца.

Пример кода

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
​
def find_fifth_from_end(head):
    first = head
    second = head
    ​
    # Перемещаем первый указатель на пять узлов вперед
    for _ in range(5):
        if first is None:
            return None  # Если список содержит меньше пяти элементов
        first = first.next
    ​
    # Перемещаем оба указателя, пока первый не достигнет конца
    while first is not None:
        first = first.next
        second = second.next
    ​
    return second.data if second else None
​
# Пример использования
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
head.next.next.next.next.next.next = Node(7)
​
result = find_fifth_from_end(head)
print(result)  # Вывод: 3

Объяснение кода

• Класс Node: Определяет структуру узла связанного списка, содержащего данные и ссылку на следующий узел.
• Функция find_fifth_from_end: Принимает голову списка и возвращает данные пятого элемента с конца.
  • Инициализация указателей: first и second указывают на голову списка.
  • Цикл for: Перемещает first на пять узлов вперед. Если список содержит меньше пяти элементов, возвращает None.
  • Цикл while: Перемещает оба указателя, пока first не достигнет конца. В этот момент second указывает на пятый элемент с конца.
• Пример использования: Создает связанный список из семи элементов и находит пятый элемент с конца, который равен 3.