数据结构 - 访谈:删除链表中的循环 - Java - data structures - Interview: Remove Loop in linked list

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

因此，有关如何解决此问题的任何指示可能是伪代码或方法定义？

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

例如，这个链表有一个循环

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

这个问题有两个部分：

检测列表中是否存在循环
确定循环的起点

一旦知道循环的开始

位置，就很容易识别列表中的最后一个元素，因为它是循环开始之后的列表中的元素，最终指向循环的开始。然后，将此元素的下一个指针/引用设置为null以更正循环链接列表(不是循环链表，这是最后一个元素指向第一个元素的地方 - 这将是循环列表的特定实例(。

也称为龟兔算法，因为它涉及使用两个以不同速度移动的指针/参考，是检测周期的一种方法。如果存在循环，则两个指针(例如p1和p2(将在有限数量的步骤后最终指向同一元素。有趣的是，可以证明它们相遇的元素与循环起点的距离(继续以相同的向前方向遍历列表(的距离与循环起点到列表的头部的距离相同。也就是说，如果列表的线性部分有k个元素，则两个指针将在长度m的循环内相遇，m-k从循环的开始或k元素到循环的"结束"(当然，它是一个循环，所以它没有"结束" - 它只是再次"开始"(。这为我们提供了一种找到循环起点的方法：
检测到循环后，让p2继续指向上述步骤的循环终止的元素，但重置p1以便它指向列表的头部。现在，一次移动一个元素的每个指针。由于p2在循环内开始，它将继续循环。经过k步(等于循环开始与列表头部的距离(，p1和p2将再次相遇。这将为您提供对循环开始的引用。
现在很容易将p1(或p2(设置为指向开始循环的元素并遍历循环，直到p1最终指向起始元素。此时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 从头部开始，在同样的速度，那么受赠人将满足在位置 0，第一个节点周期。QED。

更多参考资料：

http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
链表中查找周期开始节点？
在链表中检测周期开始的证明
Hristo在本页上对这个问题的回答也引用了一本采访书中的解释

解决方案 1 - 由 Career Cup 和"破解编码面试"一书提供：

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 步骤两者都将是循环的开始(。
现在，回到问题，当快速奔跑者(n2(和慢跑者 (n1( 正在我们的周围移动循环链表，n2 将有一个 N1 时环路领先一步进入。具体来说，它将有一个 k 的开头，其中 k 是数字循环前的节点数。由于 n2 有领先于 k 个节点，n1 和 n2 将在开始之前满足 k 个节点循环。
因此，我们现在知道以下内容：
头是来自LoopStart的k个节点(根据定义(
n1 和 n2 的交汇点是来自 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;
}

我希望这有所帮助。
Hristo

这个回答并不是为了争夺答案，而是为了解释更多关于和野兔算法中两个节点的相遇。

两个节点最终都将进入循环。因为一个移动(F(比另一个(S(快，(F(最终会圈(S(。
如果循环的起点在列表的头部，则 (F( 必须在列表的头部与 (S( 相遇。这只是因为 (F( 的速度是 2 倍 (S(;如果是 3 倍，那就不是真的了。这是正确的，因为 (F( 在 (S( 完成半圈时完成一圈，因此当 (S( 完成第一圈时，(F( 已完成两圈 - 并且以 (S( 返回循环的起点。
如果循环的开始不在列表的头部，那么当 (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(无余数(处的 POSITION 为 0。因此，就位置(或微分(而言，这留下了k(或者更确切地说，-k(。

因此，最后，(S( 和 (F( 将在远离循环起点的位置 (0 - k( 或 (k( 节点相遇。
给定上面的 [3]，由于 (k( 表示 (F( 的领先优势，并且 (F( 从列表的头部进入循环的距离是 (S( 的 2 倍，因此 (k( 也表示距离列表起点的距离，然后表示循环的开始。

这里有点晚了，所以我希望我已经有效地表达了。否则请告诉我，我会尝试更新我的回复。

如果允许使用身份哈希映射(例如 IdentityHashMap(，则非常容易解决。不过，它确实会占用更多空间。

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

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

快乐编码。

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

在链接列表的每个节点之后插入虚拟节点，并在插入之前检查下一个旁边的节点是否是虚拟节点。如果下一个是虚拟节点，则在该节点的下一个节点中插入 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

//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

最简单和独特的方式

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

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。

数据结构 - 访谈:删除链表中的循环 - Java

最简单和独特的方式

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

相关内容

最新更新

热门标签：