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

Метод 1: итеративный подход
Итеративный подход предполагает обход связанного списка с одновременным изменением порядка указателей для изменения порядка узлов. Вот пример на Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
def reverse_list(head):
    if not head or not head.next:
        return head
    prev = None
    curr = head
    tail = None
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
        if not next_node:
            tail = prev
    tail.next = head
    head = tail
    return head

Метод 2: рекурсивный подход
Рекурсивный подход включает в себя изменение подсписка, начиная со второго узла, а затем соответствующую настройку указателей. Вот пример на Java:

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class LinkedList {
    Node head;
    public Node reverseList(Node curr, Node prev) {
        if (curr == null)
            return prev;
        Node nextNode = curr.next;
        curr.next = prev;
        if (nextNode == null)
            return curr;
        return reverseList(nextNode, curr);
    }
    public void moveTailToHead() {
        if (head == null || head.next == null)
            return;
        Node tail = head;
        Node secondLast = null;
        while (tail.next != null) {
            secondLast = tail;
            tail = tail.next;
        }
        tail.next = head;
        head = tail;
        secondLast.next = null;
    }
}

Метод 3: подход стека
Используя стек, мы можем поместить все узлы в стек, а затем извлечь их один за другим, чтобы создать обращенный связанный список. Вот пример на C++:

#include <stack>
struct Node {
    int data;
    Node* next;
};
Node* reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    std::stack<Node*> stack;
    Node* current = head;
    while (current) {
        stack.push(current);
        current = current->next;
    }
    head = stack.top();
    current = head;
    stack.pop();
    while (!stack.empty()) {
        current->next = stack.top();
        stack.pop();
        current = current->next;
    }
    current->next = nullptr;
    return head;
}

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