Циркулярно связанный список удаляет хвост без цикла

Question

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

remove = tail; 
    prev  = temp = tail.getNext(); 

    do 
    { 
     prev = temp; 
     temp = temp.getNext(); 
    } 
    while(!temp.getNext().equals(tail.getNext())); 

    prev.setNext(temp.getNext()); 
    size--; 
    return remove; 

Примечание: предыдущая, температура, removeare местный и хвост хвост списка и первый экземпляр tail.getNext() является главой.

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

remove = tail; 
    tail= lastNode.getNext(); 
    size--; 
    return remove; 

Answer 1

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

Так

Node removeTail() { 
    if (head == null) { 
     return null; 
    } 

    Node tail = head.previous; 
    Node newTail = tail.previous; 
    newTail.next = head; 
    head.previous = newTail; 

    if (head == tail) { 
     head = null; 
    } 
    --size; 
    return tail; // If so desired. 
}