这个函数从尾部获取链接列表中的节点的空间和时间复杂度是多少？

Question

以下解决方案的空间和时间复杂度(最坏的情况)是什么？

Node getNodeFromTail(Node head, int x){
    Node p = head;
    Node q = head;

    int diff = 0;

    while (p.next != NULL){
        p = p.next;

        if (diff >= x)
            q = q.next;
        else
            diff++;
    }
    return q;
}

以下是对上述代码的解释：

以这个链表为例:1->2->3->4->5

X ==值从尾部，

当x为0时，结果应为5。

当x为1时，结果应为4。

当x为2时，结果应该是3，依此类推。

我就是这么想的：

空间复杂度

常空间O(1)

时间复杂度

而循环在O(n)时间中遍历链表；

其中n=链表的长度。

但是，我认为，由于if语句的复杂性，它应该是O(N) time，从而给我们留下了：O(n) *O(N)，它几乎是O(n^2) (即二次)的总体时间复杂度。

我只是有种感觉，在最坏的情况下，这并不完全是线性时间。

这是正确的吗？

参考资料：https://stackoverflow.com/a/31190255/12357170

Answer 1

时间复杂度为O(n)或线性。while循环的条件仅取决于循环中的p=p->下一条指令。循环中的其他指令是在恒定时间内执行的，不会对while循环的条件产生影响。因此，我们可以得出这样的结论:循环被执行了整整n次(如果list是n个元素)。

还请注意，第一个while循环中没有其他循环，就像您在问题中所建议的那样。