CODEWITHSUNDEEP
swiftalgorithmlinked-listtime-complexity
Nav
Nav

Reputation: 10442

What is the time complexity of the below mentioned linked list algorithm

I am writing an algorithm to remove the last N nodes from a linked list and append it to the front of the linked list as provided below

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

However I am having some difficulty calculating the time complexity of this algorithm.

As per my understanding the first for loop should be a constant O(1)

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

But, what about the second while loop, will it be O(log N) considering the fast pointer has been forwarded in linear time within the first for loop and the second while loop just continues from the last value stored? 

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

And what will be the total time complexity of this algorithm?

Upvotes: 0

Views: 119

Answers (1)

sheikh hamza
sheikh hamza

Reputation: 101

how is your first loop O(1) when it goes from start to nth element? and as n is your final element you are practically recursing through the entire list your first loop actually has O(N) and since you are at final element shouldnt it have no next element and should it not make fast?.next != nil condition false?

Upvotes: 1

Related Questions