Каким образом можно добавить элемент в середину связанного списка так, чтобы операция выполнялась за постоянное время?

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

Если же у вас есть только ссылка на голову списка, то для поиска середины потребуется пройти половину списка — это уже O(n).

Пример вставки после заданного узла в Java:

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

void insertAfter(Node node, int newValue) {
    Node newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
}

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