691 views
0 votes
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).

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
Pragyanshu Singh asked Jan 26, 2019
324 views
IF the above network uses class C network 192.203.16.0; Then find the DBA used for Dept Y
0 votes
0 votes
0 answers
2
Gate Fever asked Jan 14, 2019
803 views
(i)A computer can have multiple MAC addresses(ii)A computer can have multiple IP addresses at different instances of timetrue/ false??acc to me(i) false (ii)true
0 votes
0 votes
0 answers
4
Gate Fever asked Jan 12, 2019
676 views
consider a system with 48 bit virtual address and page size is 16KB.Operating system uses multilevel paging.page table entry size is 4B.What is the number of entries in t...