面试：删除链表中的循环 - Java

Question

我在面试中被问到这个问题：“如何检测链表中的循环？”，我解决了这个问题，但面试官立即问我如何删除链表中的循环。我摸索着。

那么关于如何解决这个问题的任何指示可能是伪代码或方法定义？

我对 Java 很熟悉，所以我在 java 下标记了这个问题。

例如这个链表有一个循环

 0--->1---->2---->3---->4---->5---->6
                  ▲                 |
                  |                 ▼
                 11<—-22<—-12<—-9<—-8

Answer 1

这个问题有两个部分：

1. 检测列表中是否存在循环
2. 识别循环的开始

一旦知道循环开始的位置，就很容易识别列表中的最后一个元素，因为它是列表中紧随循环的开始，最终指向循环的开始。然后，将此元素的下一个指针/引用设置为 null 来纠正循环链接列表（不是循环链接列表，循环链接列表是最后一个元素指向第一个元素的位置 - 这将是一个循环列表的具体实例）。

1. Floyd 的循环检测算法，也称为龟兔算法，因为它涉及使用以不同速度移动的两个指针/参考是检测周期的一种方法。如果存在循环，则两个指针（例如 p1 和 p2）将在有限数量的步骤后最终指向同一个元素。有趣的是，可以证明它们相遇的元素到循环开始的距离与开始的距离相同（继续以相同的向前方向遍历列表）循环的位置是列表的头部。。也就是说，如果列表的线性部分有 k 个元素，则两个指针将在长度为 m 的循环内于点 mk 处相遇从循环的开始或 k 元素到循环的“结束”（当然，这是一个循环，因此它没有“结束” - 它只是再次“开始”）。这为我们提供了一种找到循环起点的方法：

2. 一旦检测到循环，让p2保持指向上述步骤的循环终止但重置的元素>p1 以便它指向列表的头部。现在，将每个指针一次移动一个元素。由于 p2 在循环内部开始，因此它将继续循环。经过 k 步（等于循环起点到列表头部的距离）后，p1 和 p2 将再次相遇。这将为您提供循环开始的引用。

3. 现在可以轻松设置p1（或p2）以指向开始循环的元素并遍历循环直到p1结束up 指向起始元素。此时 p1 正在引用“最后一个”元素列表，并且它的下一个指针可以设置为 null。

---

下面是一些快速而肮脏的 Java 代码，假设有一个 Node 的链接列表，其中 Node 具有 next 引用。这可以优化，但它应该给你基本的想法：

Node slow, fast, start;
fast = slow = head;

//PART I - Detect if a loop exists
while (true)
{
    // fast will always fall off the end of the list if it is linear
    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; // move 2 nodes at at time
        slow = slow.next; // move 1 node at a time
    }
}

//PART II - Identify the node that is the start of the loop
fast = head; //reset one of the references to head of list

//until both the references are one short of the common element which is the start of the loop
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; //break the loop

---

这个解释可能有助于解释第二部分背后的原因：

假设循环长度为M，
和其余部分的长度
链表是L。我们来算一下
在循环中处于什么位置时
t1/t2 第一次见面？

定义循环中的第一个节点是
位置 0，按照我们的链接
位置为 1、2、...，直至 M-1。 （
当我们走在循环中时，我们当前的
位置是 (walk_length) mod M，
对吗？）假设 t1/t2 第一次相遇于
位置 p，那么他们的旅行时间是
同样，(L+k1*M+p)/v = (L+k2*M+p)/2v
对于一些k1

因此得出的结论是，如果 t1 从
p, t2 从 head 开始移动到
同样的速度，然后受赠者会面
在位置 0 处，第一个节点
循环。量子ED。

更多参考：

• http://www .quora.com/How-does-Floyds-cycle-finding-algorithm-work
• 解释如何在循环链表中查找循环起始节点？
• 检测链表中循环开始的证明
• Hristo 在本页对此问题的回答还引用了采访书中的解释

Answer 2

解决方案 1 - 由职业杯和《破解编码面试》一书提供：

public static LinkedListNode findStartOfLoop(LinkedListNode head) {
    LinkedListNode n1 = head;
    LinkedListNode n2 = head; 

    // find meeting point using Tortoise and Hare algorithm
    // this is just Floyd's cycle detection algorithm
    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;
}

此解决方案的解释直接来自书本：

如果我们移动两个指针，其中一个指针带有
速度 1 和另一个速度 2，他们
如果已链接，则最终会面
列表有一个循环。为什么？想想两个
在轨道上行驶的汽车；更快的车
总是会超过较慢的那一个！

这里棘手的部分是找到起点
循环的。想象一下，打个比方，
两个人绕跑道赛跑，
一个人跑得比别人快一倍
其他。如果他们同时开始
地点，下次见面是什么时候？他们
将在下次会议开始时
下一圈。

现在，假设 Fast Runner 领先了 k 米
n 步一圈。他们下次什么时候
见面？他们将在 k 米之前相遇
下一圈的开始。 （为什么？快
跑步者会做出 k + 2(n - k)
步骤，包括领先优势，以及
慢跑者会做出 n - k
步骤 两者都将是之前的 k 步
循环开始）。

现在，回到问题，当 Fast Runner (n2) 和
慢跑者（n1）正在我们周围移动
循环链表，n2 将有一个
当 n1 时，循环开始
进入。具体来说，它将有一个
k 的开头，其中 k 是数字
循环之前的节点数。由于 n2 有
k 个节点 n1 和 n2 的领先优势
开始之前会遇到 k 个节点
循环。

所以，我们现在知道以下内容：

1. Head 是来自 LoopStart 的 k 个节点（根据定义）
2. n1 和 n2 的 MeetingPoint 是 LoopStart 中的 k 个节点（如上所示）

因此，如果我们将 n1 移回 Head 并将 n2 保留在 MeetingPoint，并以相同的速度移动它们，它们将在 LoopStart 处相遇

解决方案 2 上见面 - 由我提供:)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexer = 0;
    Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
    map.put(head, indexer);
    indexer++;

    // start walking along the list while putting each node in the HashMap
    // if we come to a node that is already in the list, 
    // then that node is the start of the cycle 
    LinkedListNode curr = head;
    while (curr != null) {

        if (map.containsKey(curr.next)) {
            curr = curr.next;
            break;
        }
        curr = curr.next;
        map.put(curr, indexer);
        indexer++;
    }
    return curr;
}

我希望这会有所帮助。
赫里斯托

Answer 3

这个回答并不是为了争夺答案，而是为了进一步解释一下龟兔赛跑算法中两个节点的相遇。

1. 两个节点最终都会进入循环。因为一个 (F) 移动得比另一个 (S) 快，所以 (F) 最终会绕 (S)。

2. 如果循环的起点位于列表的头部，则 (F) 必须在列表的头部与 (S) 相遇。这只是因为 (F) 的速度是 (S) 的 2 倍；如果是 3X，则事实并非如此。这是正确的，因为当 (S) 完成半圈时，(F) 也完成一圈，因此当 (S) 完成第一圈时，(F) 已经完成两圈 - 并且与 (S) 一起回到循环起点.

3. 如果循环的起点不在列表的头部，则当 (S) 进入循环时，(F) 已在循环中从 (k) 个节点开始。因为 (S) 的速度一次只有一个节点，所以它将在从循环开始起的 (k) 个节点处与 (F) 相遇 - 例如，在到达起点之前还需要 (k) 步，而不是在到达起点之后的 (k) 步开始。如果 (S) 的速度不是 1 并且 (F) 和 (S) 之间的速度比不是 2:1，则情况不成立。

   3.1。这就是解释起来有点棘手的地方。我们可以同意 (F) 将继续重叠 (S) 直到它们最终相遇（参见上面的 1），但是为什么在从循环开始起的 (k) 个节点处呢？考虑以下等式，其中 M 是节点数或环路距离，k 是领先起点 (F)；该方程将左侧给定时间 t 下 (F) 行驶的距离换算为右侧 (S) 行驶的距离：

   d_F(t) = 2 * d_S(t) + k

   因此，当 (S) 进入循环并在循环中行进了 0 距离时，(F) 只行进了 (k) 距离。当 d_S = M - k 时，d_F = 2M - k。因为我们还必须使用模数学，考虑到 M 代表循环中单圈的总距离，所以 (F) 和 (S) 在任何整个 M（无余数）处的位置为 0。因此，根据POSITION（或微分），这留下 k（或更确切地说，-k）。

   最后，(S) 和 (F) 将在距离循环起点 (0 - k) 或 (k) 个节点处相遇。

4. 根据上面的[3]，as (k) 表示领先位置 (F)，并且 as (F) 已经移动了从列表头部进入循环的距离 (S) 的 2 倍，(k)也表示距列表起点的距离，该距离代表循环的起点。

现在有点晚了，所以我希望我已经表达清楚了。否则请告诉我，我会尝试更新我的回复。

Answer 4

如果使用身份哈希映射（例如 IdentityHashMap) 是允许的，这非常容易解决。不过，它确实使用了更多空间。

遍历节点列表。对于遇到的每个节点，将其添加到身份映射中。如果该节点已存在于身份映射中，则列表具有循环链接，并且在此冲突之前的节点是已知的（在移动之前检查或保留“最后一个节点”）——只需根据需要设置“下一个”即可打破循环。

遵循这个简单的方法应该是一个有趣的练习：代码留给读者作为练习。

快乐编码。

Answer 5

 0--->1---->2---->3---->4---->5---->6
                  ▲                 |
                  |                 ▼
                 11<—-22<—-12<—-9<—-8  

在链表的每个节点之后插入虚拟节点，并在插入之前检查下一个节点是否为虚拟节点。如果 next to next 是虚拟的，则在该节点的 next 中插入 null。

 0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6
                     ▲                      |
                  /                         ▼
                 11<—D<-22<—D<-12<—D<-9<—D<--8 


Node(11)->next->next == D
Node(11)->next =null

Answer 6

//Find a Loop in Linked List and remove link between node

    public void findLoopInList() {
            Node fastNode = head;
            Node slowNode = head;
            boolean isLoopExist = false;
            while (slowNode != null && fastNode != null && fastNode.next != null) {
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
                if (slowNode == fastNode) {
                    System.out.print("\n Loop Found");
                    isLoopExist = true;
                    break;
                }
            }
            if (isLoopExist) {
                slowNode = head;
                Node prevNode = null;
                while (slowNode != fastNode) {
                    prevNode = fastNode;
                    fastNode = fastNode.next;
                    slowNode = slowNode.next;
                }
                System.out.print("Loop Found Node : " + slowNode.mData);
                prevNode.next = null; //Remove the Loop
            }
        }

:)GlbMP

Answer 7

最简单且独特的方法

为了解决这个问题，我们只需计算节点数（就是这样）。 我敢打赌，到目前为止，您还没有在任何竞争性网站上看到过这个解决方案，因为我今天自己做到了......

void removeTheLoop(Node *root)
{
    std :: unordered_set < struct Node * > s;
    if(root == NULL)
        return ;

    s.insert(root);
    int before_size = s.size();

    while(1)
    {
        if(root -> next == NULL)
            return;
        s.insert(root -> next);
        if(before_size == s.size())
        {
            root -> next = NULL;
            return;
        }
        before_size = s.size();
        root = root -> next;
    }
}

它是如何工作的：

时间复杂度：O(n)...空间复杂度：O(n)

• 它只是计算元素的数量。我们将采用 c++ 中的 unordered_set 。
• 如果容器中不存在该元素，它将插入该元素并增加其大小。
• 现在，当节点指向已添加的节点时，悬念就开始了，因此在这种情况下，大小不会增加，我们会将其旁边的值设置为 NULL。

如果您认为它是独一无二的，请投票。