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

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

x==尾部的值，
当x为0时，结果应为5
当x为1时，结果应为4
当x为2时，结果应为3，依此类推。

这是我的想法：
空间复杂性
恒空间O（1）

时间复杂度
while循环在O（n）时间内遍历链表
其中n=链表的长度。

然而，我认为由于if语句，它有一个额外的复杂性，我觉得应该是O（n-x）时间，因此留给我们的是：O（n）*O（n-x），这几乎是O（n^2）的总体时间复杂性（即二次）<我只是有一种感觉，在最坏的情况下，这并不完全是线性时间<这是正确的吗？

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

Answer 1

时间复杂度为O（n）或线性。while循环的条件仅取决于p=p-