Pergunta de entrevista da empresa Microsoft
Given 2 LinkedList ListNode pointers, determine if the two lists ever intersect. Building upon that, if they do intersect, at what node. Building on that, what do you do if there is a circle in the list, and can you detect one
Resposta da entrevista
Sigiloso
1. You can just iterate through one linkedList one node at a time, and the whole list of the other one. If you in any iteration the nodes are the same, then they intersect. 2. Iterate through the list with two pointers, one moves one at a time, the other moves two at a time. If they meet then there is a circle, if they don't they will see a null node and stop. 3. An easy way is to mark the point in the circle. Use two pointers. One to iterate from the beginning of the list, one index at a time. The other one starts from the marked point and iterate until it's at the marked position again. So the first pointer is walking one step at a time, and the other pointer is running a whole circle every time the first pointer makes one step. When the first pointer is in the circle, the second pointer will meet him while it was running circles. Cracking the coding interview has a better solution.