798 views
0 votes
0 votes
What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.? Please mention the reason of the answer also.

1 Answer

Best answer
0 votes
0 votes

If you want to find the 8$^{th}$ element from the beginning of the linked list then

=>you have to move 8 steps from the starting of the link list

=> this requires constant time

=> T.C. = O(1).

------------------------------------------------------------------------------------------------------------------------------

If you want to find the 8$^{th}$ element from the end of the linked list then

=> you have to move till the end of the linked list.......O(n)

=> calculate the position of the 8$^{th}$ element from the end of the linked list .....O(1)

=> then you have to start again from starting of the linked list (since you cannot move backwards in a linked list) and move the pointer till you reach the 8$^{th}$ element from the end of the linked list .....O(n)

=> T.C. = O(n) + O(1) +O(n) = O(n).

OR

=> reverse the linked list .........O(n)

=> find the  8$^{th}$ element from the starting of the reversed linked list.....O(1)

=> T.C. = O(n) + O(1)  = O(n).

OR

keep two pointers, named as first and second,

move the second pointer 8 steps, and stop it !

now until you find second->next = NULL, for each iteration forward first and second pointers simultaneously.

when you reached the end of the list, the first pointer points to the 8$^{th}$ element from the end due to the difference between them is 8 steps.

traversing of linked list takes O(n) time.

edited by

Related questions

0 votes
0 votes
1 answer
1
Mrityudoot asked Feb 25
144 views
How can we find the highest element in a singly linked list in O(1)? We are free to use any extra space.
9 votes
9 votes
2 answers
4
GO Classes asked May 4, 2022
483 views
If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n)),$ then it is always true that$f(n) = o(g(n)).$$f(n) = \theta(g(n)).$$f(n) = \omega(g(n)).$both A and B are always true.