单链表enqueue方法的Big O时间复杂度是多少？

你的O(1)判断是错误的，这段代码的平均、最坏时间复杂度都是O(n)。

判定理由 #

• 空链表分支确实是O(1)：当链表头节点为null时，直接把新节点设为头节点就返回，操作步数固定，但这个场景只在第一次入队时出现，属于特殊边界情况，不能代表整体复杂度。
• 非空场景的遍历操作是复杂度核心：非空时你需要从头节点开始，通过while循环逐次向后遍历next指针，直到找到最后一个节点才能挂载新节点。你观察到的“循环迭代次数取决于链表元素数量”，恰恰是O(n)复杂度的典型特征——操作步数和输入规模n（即链表当前元素总数）呈线性正相关：链表有n个元素时，你需要遍历n-1个节点才能到尾部，遍历步数随n增长等比例增加，完全符合O(n)的定义。

O(1)入队的优化方式 #

如果要实现O(1)时间的入队，只需要给链表额外维护一个始终指向尾节点的tail指针：入队时直接把新节点挂到tail.next，再更新tail指向新节点即可，全程不需要遍历，操作步数和链表长度无关。

对应实现代码 #

public Node<T> enqueue(T data){
        Node<T> toQueue = new Node<>(data);
        if (this.head == null) {
            this.head = toQueue;
            return toQueue;
        }
        Node<T> lastNode = this.head;
        while(lastNode.next != null){
            lastNode = lastNode.next;
        }

        lastNode.next = toQueue;

        return toQueue;
    }

内容的提问来源于stack exchange，提问作者GeRmAnImAl