下面提到的链表算法的时间复杂度是多少

Question

我正在编写一个算法，从链表中删除最后N个节点，并将其附加到链表的前面，如下所示

func removeAndAppendLastToFront(N: Int) {
    var slow: Node? = head
    var fast: Node? = head

    for _ in 0 ..< N - 1 {
        fast = fast?.next
    }

    var previous: Node?
    while fast?.next != nil {
        previous = slow
        slow = slow?.next
        fast = fast?.next
    }

    if previous != nil {
        previous?.next = nil
        fast?.next = head
        head = slow
    }
}

然而，我在计算该算法的时间复杂度时遇到了一些困难。

根据我的理解，第一个for循环应该是一个常数O（1）

 for _ in 0 ..< N - 1 {
        fast = fast?.next
 }

但是，第二个while循环会是O（logn）吗？考虑到快速指针在第一个for循环中以线性时间转发，而第二个while循环仅从存储的最后一个值继续？

  while fast?.next != nil {
        previous = slow
        slow = slow?.next
        fast = fast?.next
  }

这个算法的总时间复杂度是多少？

Answer 1

当第一个循环O（1）从开始到第n个元素时，它是如何运行的？因为n是你的最后一个元素，你实际上是在整个列表中递归，你的第一个循环实际上有O（N），因为你在最后一个元素，它不应该有下一个元素，它不应该快吗？。下一个！=nil条件false？