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

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 循环怎么样，考虑到快速指针已经在第一个 for 循环内以线性时间转发，而第二个 while 循环只是从最后存储的值继续，它会是 O(log N) 吗？

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

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

Answer 1

从开始到第 n 个元素，你的第一个循环 O(1) 怎么样？由于 n 是您的最后一个元素，您实际上是在遍历整个列表你的第一个循环实际上有 O(N) 并且因为你在最后一个元素不应该没有下一个元素并且它不应该快速吗？.next != nil 条件 false？