访谈:移除链表中的循环 - Java
在这篇文章中,讨论了如何在链表中找到并删除循环。作者通过介绍龟兔算法中两个节点相遇的原因来解释了这个问题。
文章首先指出,由于兔子节点的速度比乌龟节点快,它们最终都会进入循环。如果循环的起点在链表的头部,兔子节点最终会在链表的头部再次遇到乌龟节点。这是因为兔子节点的速度是乌龟节点的两倍。
然后,文章讨论了如果循环的起点不在链表的头部,那么乌龟节点进入循环时,兔子节点已经在循环中领先了k个节点的距离。由于乌龟节点每次只能移动一个节点,它会在离循环起点k个节点的位置遇到兔子节点。这是因为兔子节点每次移动距离是乌龟节点的两倍。
接着,文章通过一个方程来解释为什么兔子节点和乌龟节点会在离循环起点k个节点的位置相遇。方程是d_F(t) = 2 * d_S(t) + k,其中d_F(t)表示兔子节点在时间t内移动的距离,d_S(t)表示乌龟节点在时间t内移动的距离,k表示兔子节点在乌龟节点进入循环时的领先距离。通过解方程,可以得出兔子节点和乌龟节点在离循环起点k个节点的位置相遇。
最后,文章指出k不仅表示兔子节点在循环中的领先距离,也表示链表起点到循环起点的距离。
总结一下,这篇文章通过解释龟兔算法中两个节点相遇的原因,介绍了解决链表中循环问题的方法。
问题:如何移除链表中的循环?
在这个问题中,我们需要解决的是如何找到循环链表的起点并移除循环。下面给出了两种解决方案。
解决方案1:使用乌龟和兔子算法
我们可以使用乌龟和兔子算法来找到循环的起点。算法的原理是,当两个指针以不同的速度遍历链表时,如果链表存在循环,它们最终会相遇。具体步骤如下:
1. 初始化两个指针n1和n2,都指向链表的头节点head。
2. 使用乌龟和兔子算法,n1每次移动一步,n2每次移动两步,直到它们相遇为止。
3. 如果n2的下一个节点为空,则说明链表不存在循环,返回null。
4. 将n1移回到链表的头节点,然后同时移动n1和n2,每次移动一步,直到它们再次相遇。
5. 此时,n2指向循环的起点,返回n2。
解决方案2:使用HashMap
另一种解决方案是使用HashMap,但是这种方法只适用于链表中的元素是唯一的情况。具体步骤如下:
1. 初始化一个索引变量indexer为0,并创建一个空的HashMap。
2. 将链表的头节点head放入HashMap中,键为head,值为indexer,并将indexer加1。
3. 从头节点开始遍历链表,将每个节点放入HashMap中,如果遇到已经在HashMap中存在的节点,则说明该节点是循环的起点,将其返回。
4. 如果遍历完整个链表都没有找到循环的起点,则返回null。
通过以上两种解决方案,我们可以找到循环链表的起点并移除循环。解决方案1使用了乌龟和兔子算法,解决方案2使用了HashMap。这两种方法各有优劣,我们可以根据具体情况选择合适的方法来解决问题。
这个问题的出现原因是要解决链表中的循环问题。问题可以分为两个部分:检测链表中是否存在循环以及找到循环的起点。一旦知道循环的起点,就可以很容易地找到链表的最后一个元素,因为它是在循环起点之后指向循环起点的元素。然后,可以将最后一个元素的下一个指针设置为null,以修复循环链表。
要检测循环,可以使用弗洛伊德循环检测算法(也称为乌龟和兔子算法)。该算法使用两个指针,分别以不同的速度移动,如果存在循环,这两个指针将在有限步骤后指向同一个元素。有趣的是,可以证明它们相遇的位置将与循环的起点到链表头的距离相同。因此,可以使用这种方法找到循环的起点。
一旦检测到循环,可以让其中一个指针指向循环结束的元素,然后让另一个指针指向链表头。接下来,每次移动一个元素,两个指针将再次相遇。这将给出循环的起点的引用。
现在可以将一个指针指向循环的起点,并遍历循环,直到该指针指向起点。此时,该指针引用的是链表的“最后”一个元素,可以将其下一个指针设置为null,以打破循环。
下面是一个使用Java实现的示例代码:
Node slow, fast, start; fast = slow = head; // PART I - Detect if a loop exists while (true) { if (fast == null || fast.next == null) { // no loop return; } else if (fast == slow || fast.next == slow) { // detected a loop break; } else { fast = fast.next.next; slow = slow.next; } } // PART II - Identify the node that is the start of the loop fast = head; while (fast.next != slow.next) { fast = fast.next; slow = slow.next; } start = fast.next; // PART III - Eliminate the loop by setting the 'next' pointer // of the last element to null fast = start; while (fast.next != start) { fast = fast.next; } fast.next = null;
这段代码首先使用两个指针检测链表中是否存在循环。然后,根据检测到的循环,找到循环的起点。最后,通过遍历循环,将最后一个元素的下一个指针设置为null,从而消除循环。
以上是关于解决链表中循环问题的方法和示例代码。希望对你有所帮助!