Cracking the Coding Interview,第6版,2.8

Question

问题陈述:给定一个循环链表,实现一个在循环开始时返回节点的algoirthm.

答案密钥提供了比我建议的更复杂的解决方案.我有什么问题？:

public static Node loopDetection(Node n1) {
    ArrayList<Node> nodeStorage = new ArrayList<Node>();

   while (n1.next != null) {
       nodeStorage.add(n1);
       if (nodeStorage.contains(n1.next)) {
           return n1;
       }
       else {
           n1 = n1.next;
       }
   }

   return null;
}

Answer 1

您的解决方案是O(n^2)时间(每个contains()中ArrayList为O(n)时间)和O(n)空间(用于存储nodeStorage),而"更复杂"的解决方案是O(n)时间和O(1)空间.

本书为感兴趣的人提供了以下解决方案:O(n)时间和O(1)空间:

如果我们移动两个指针,一个速度为1,另一个速度为2,如果链表有循环,它们将会结束.为什么？想想两辆在赛道上行驶的汽车 - 速度越快的汽车总会越过慢速汽车!这里棘手的部分是找到循环的开始.想象一下,作为一个类比,两个人在赛道上比赛,一个赛跑的速度是另一个赛车的两倍.如果他们在同一个地方开始,他们下一次会什么时候见面？接下来他们将在下一圈开始时见面.现在,让我们假设Fast Runner在n步圈上有一个k米的起跑线.他们什么时候下次见面？他们将在下一圈开始前达到k米.(为什么？快跑者会做出k + 2(n-k)步,包括它的头部开始,慢跑者会做n-k步.两者都将在循环开始之前的k步.)现在,回到问题,当Fast Runner(n2)和Slow Runner(n1)在我们的循环链表中移动时,当n1进入时,n2将在循环上有一个开头.具体来说,它将具有k的头部起点,其中k是循环之前的节点数.由于n2具有k个节点的头部起始,因此n1和n2将在循环开始之前与k个节点相遇.因此,我们现在知道以下内容:1.Head是来自LoopStart的k个节点(根据定义).2. MeetingPoint for n1和n2是来自LoopStart的k个节点(如上所示).因此,如果我们将n1移回Head并在MeetingPoint保持n2,并以相同的速度移动它们,它们将在LoopStart上相遇.它将具有k的头部起点,其中k是循环之前的节点数.由于n2具有k个节点的头部起始,因此n1和n2将在循环开始之前与k个节点相遇.因此,我们现在知道以下内容:1.Head是来自LoopStart的k个节点(根据定义).2. MeetingPoint for n1和n2是来自LoopStart的k个节点(如上所示).因此,如果我们将n1移回Head并在MeetingPoint保持n2,并以相同的速度移动它们,它们将在LoopStart上相遇.它将具有k的头部起点,其中k是循环之前的节点数.由于n2具有k个节点的头部起始,因此n1和n2将在循环开始之前与k个节点相遇.因此,我们现在知道以下内容:1.Head是来自LoopStart的k个节点(根据定义).2. MeetingPoint for n1和n2是来自LoopStart的k个节点(如上所示).因此,如果我们将n1移回Head并在MeetingPoint保持n2,并以相同的速度移动它们,它们将在LoopStart上相遇.

LinkedListNode FindBeginning(LinkedListNode head) {
   LinkedListNode n1 = head;
   LinkedListNode n2 = head;

   // Find meeting point
   while (n2.next != null) {
      n1 = n1.next;
      n2 = n2.next.next;
      if (n1 == n2) {
         break;
      }
   }
// Error check - there is no meeting point, and therefore no loop
   if (n2.next == null) {
      return null;
   }
   /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
   /* from the Loop Start. If they move at the same pace, they must
   * meet at Loop Start. */
   n1 = head;
   while (n1 != n2) {
      n1 = n1.next;
      n2 = n2.next;
   }
   // Now n2 points to the start of the loop.
   return n2;
   }