[google面试题]How can one determine whether a singly linked list has a cycle?
Good answer: Keep track of two pointers in the linked list,and start them at thebeginning of the linked list.At each iteration of the algorithm,advance the firstpointer by one node and these condpointer by two nodes.If the two pointers areever the same(other than at the beginning of the algorithm),then there is a cycle.If a pointer ever reaches the end of the linked list before the pointers are the same,then there is no cycle.Actually,the pointers need not move one and two nodes at the same;it is only necessary that the pointers move at different rates.This takes O(n) time.This is a tricky answer that interviewers really like for some reason.Okay answer:For every node you encounter while going through the list one by one,put a pointer to that node in to a O(1)‐look up time data structure,such as a hashset.Then, when you encounter a new node,see if a pointer to that node already exists in your hashset.This should take O(n) time, but also takes O(n) spaceOkay answer:Go through the elements of the list."Mark" each node that your each.If your each a marked node before reaching the end,the list has a cycle; otherwise,it doesnot.This also takes O(n) time.
页:
[1]