Write a fast algorithm to detect whether a linked list L is a "conventional singly linked list" or a "loop singly linked list". The input to the algorithm is a linked list L$,$ which is either a conventional singly linked list or a loop singly linked list. The algorithm outputs $"$It is a conventional singly linked list" if L is a conventional singly linked list; outputs $"$It is a loop singly linked list" if L is a loop singly linked list.

You are required to

describe the idea of your algorithm,

present the pseudo code or java code of your algorithm $($please use comments to make your code easy to understand$),$ and

analyze the running time of your algorithm.

Remark $1$: You can only call the methods getHead and getNext. You cannot call other methods. L$.$getHead$()$ returns the head of L$.$ If x is a node, x$.$getNext$()$ returns the next node of x$.$

Remark $2$: You will get full credits $(30$ points$)$ if your algorithm is correct, the running time analysis is correct, and your algorithm is fast. Fast means that the running time of your algorithm where n is the number of nodes. You will get partial credits $(25$ points$)$ if your algorithm is correct, the running time analysis is correct, but the running time of your algorithm $.$