java - 循环链表去除尾部没有循环

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;

注意:prev、temp、remove 是局部的，tail 是列表的尾部，tail.getNext() 的第一个实例是头部。

我也尝试了下面的方法，但它不起作用，因为 tail 之前的节点仍然指向 tail 并且引用没有被删除。我知道我需要将尾部的前一个点指向头部以删除尾部，上面的代码就是这样做的，但我只是不确定如何做到这一点，以及是否有可能不循环遍历列表..

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

Answer 1

在循环链表中，每个节点都有一个previous和next。有head指针指向第一个节点，它的previous是尾节点，next是头节点。

所以

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.
}