162 views

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)

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

| 162 views
0
###
0

my approach(please see if it is correct or not)

algo

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)

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

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

0
then step 1 will not be there and still T.C. = O(n)
0
No doubt. Ans should be b.
+1
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.
0 May be there is misprint in the answer... As according to their explanation, the answer is (b)

0
Yeah. Thats what I said earlier.
0
Thank you