破解编码面试，第 6 版，2.8

Question

问题陈述：给定一个循环链表，实现一个算法returns循环开始的节点。

答案键给出了比我建议的更复杂的解决方案。我的怎么了？:

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)次（ArrayList中的每个contains()是O(n)次）和O(n)space（用于存储nodeStorage),而"more complicated"的解是O(n)时间和O(1)space.

本书提供了以下解决方案，有兴趣的可以参考，即O(n)时间和O(1)space：

If we move two pointers, one with speed 1 and another with speed 2, they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one! The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap. Now, let’s suppose Fast Runner had a head start of k meters on an n step lap. When will they next meet? They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.) Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will have a head start on the loop when n1 enters. Specifically, it will have a head start of k, where k is the number of nodes before the loop. Since n2 has a head start of k nodes, n1 and n2 will meet k nodes before the start of the loop. So, we now know the following: 1. Head is k nodes from LoopStart (by definition). 2. MeetingPoint for n1 and n2 is k nodes from LoopStart (as shown above). Thus, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at 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;
   }

Answer 2

有amit给出的解决方案。问题是你要么知道要么不知道，但你在面试中将无法弄清楚。因为我从来没有需要在链表中找到一个循环，所以知道它对我来说除了通过面试之外毫无意义。因此，对于面试官来说，将其陈述为面试问题并期待 amir 的回答（这很好，因为它具有线性时间和零额外 space），这是非常愚蠢的。

所以你的解决方案基本没问题，除了你应该使用散列table，而且你必须确保散列table散列对节点的引用[=18] =] 而不是节点。假设您有一个节点包含一个字符串和一个 "next" 指针，哈希函数对字符串进行哈希处理，如果字符串相等，则比较节点是否相等。在那种情况下，您会发现第一个具有重复字符串的节点，而不是循环开始处的节点，除非您很小心。

（amir 的解决方案在 == 比较对象而不是引用的语言中有一个非常相似的问题。例如在 Swift 中，您必须使用 === （比较引用）和不是 ==（比较对象））。

Answer 3

我很难想象这个算法是怎么回事。希望这对其他人有帮助。

在时间 t = k(3)，p2 到 head(0) 的距离是 p1 的两倍，所以要让他们回到队列中，我们需要 p2 到 'catch up' 到 p1 并且它将需要 L - k(8) 5 个步骤才能发生。 p2 的行进速度是 p1 的 2 倍。

在时间t = k + (L - k) (8)，p2需要向前走k步才能回到k。如果我们将 p1 重置回 head(0)，我们知道如果 p2 以与 p1 相同的速度行进，p1 和 p2 将在 k（分别为 3、19）处相遇。

破解编码面试，第 6 版，2.8

Cracking the Coding Interview, 6th edition, 2.8

java

algorithm

big-o

linked-list

time-complexity