Can i do this question in O(n) complexty

#1

if yes,please give some hint to solve it

#2

Yes you can do.
You can use the floyd algo or the hashing based approach.
Refer the approaches from here