The Gateway to Computer Science Excellence
0 votes

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

  1. O(1), O(1)
  2. O(n), O(1)
  3. O(n), O(n)
  4. O(n2), O(1)

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

in Algorithms by (91 points) | 126 views

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)

$K^{th}$ node from last is $(n-k+1)^{th}$   node from beginning so why we can't find in O(n)??

@Satbir i think n (no. of nodes) is already given in question.

then step 1 will not be there and still T.C. = O(n)
No doubt. Ans should be b.
B. Whenever in doubt, just check their given solution. Sometimes the incorrect setting of key is a human error (maybe typing mistake), and correct answer is mentioned in their solution instead.

May be there is misprint in the answer... As according to their explanation, the answer is (b)

Yeah. Thats what I said earlier.
Thank you

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,159 answers
93,766 users