The time and space complexity of the most efficient algorithm designed to find the kth node from the end of a linked list which has n nodes is
The answer given is d.
Why is it not option b ??
To check kth node from end, its enough to have a slow pointer which starts after kth position. By the time last node is reached, the slow pointer will be in the kth node from end. So its only O(n).
my approach(please see if it is correct or not)
1. first find N by traversing the list till end and incrementing a counter(n) for each node. -> O(n)
2. then do N-k+1 to find the node to be found from starting of linked list. -> O(1)
3. then again traverse till the desired node from starting of linked list. -> O(n).
so T.C = O(n) + O(n) = O(n)
@Satbir i think n (no. of nodes) is already given in question.
May be there is misprint in the answer... As according to their explanation, the answer is (b)