Finding a Loop in a Single Linked List
Recently, I had an interview with Rikard Gillemyr, VP Engineering of Opera Software. It was great experience that I talked to someone like him.
While interviewing, he gave me a simple data structure question (It has been a while since I worked on algorithm b/c joining the army, so I would say it was not that easy for me), and it was ‘finding a loop in a single linked list.’
A single linked list is used as a stack. It is made of nodes where each node has a pointer to the next node or null to end the list. If there is a loop between any nodes inside of single linked list, then it might not get to the end node or contain more then two links to some node.
I found a solution (but not efficient), and it was checking the entire list everytime when a node gets to next node. It ends up with O(n^2) time complexity.
He tried to give me some idea so that I can improve this, but I could not. I got mad to myself little bit, so I tried find better solution without looking or googling anything, and I found one.
If we know the first and last node, and then we reverse the list, we can track back from last node to first node. If it does not get to the first node that we started before we reverse the list, then we can say there is a loop in this single linked list. It ends up with O(n) time complexity.
Eventually, I googled this to check whether there is better answer, and I found a website.
Link to http://ostermiller.org/find_loop_singly_linked_list.html
Like I said, it has been two years not working or reviewing on any algorithm stuff, so before I start refreshing my knowledge, this was very good point to start with. I really enjoyed and had fun.
Thank you, Mr.Gillemyr
