如何去除数据结构中单链表的尾部

Question

我们不能轻易地删除单链表的最后一个节点。即使我们维护一个直接指向列表中最后一个节点的尾部引用，我们也必须能够在最后一个节点之前访问该节点，以便删除最后一个节点。但是我们不能通过从尾部跟随下一个链接到达尾部之前的节点。访问此节点的唯一方法是从列表的开头开始，在整个列表中进行搜索。但是这样一系列的链路跳转操作可能需要很长时间。

Answer 1

只需取一个从i=0到i的for循环

请参见下面的方法。

public void removeLast() {
        Node<E> next=head;
        for(int i=0; i<size; i++) {
            if(next.getNext().getNext()==null) {
                next.getNext().setNext(null);
                tail=next.getNext();
                size--;
            }
            next=next.getNext();
        }
    }

注意：getNext（）返回下一个节点的引用。

因为getNext（）返回Node类型引用，所以我们可以调用next.getNext（）. getNext（）

size保留到目前为止创建的节点数。

Answer 2

删除单链表中的最后一个节点至少需要O（n）个时间复杂度。

但是，这可以通过使用双链表在O（常量）中完成。