从下一个节点重复使用指针在LinkedList到随机节点相距 [英] Duplicate a LinkedList with a pointer to a random node apart from the next node

问题描述

问：链表的每个节点都有一个随机指针（除了下一指针），其可以随机指向另一节点或为空。你会如何​​复制这样一个链表？

Q: Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a linkedlist?

答：这是我有，我只是想批准，如果这是这样做的最佳方式

A: Here's what I have, I just wanted to ratify if this was the optimal way of doing it.

由于没有指定任何空间的限制有，我将使用 LinkedHashSet 和的LinkedHashMap （我想象人们点头他们的头已经不同意;））

Since there's no space constraints specified, I'm going to use a LinkedHashSet and a LinkedHashMap (I can imagine people nodding their head in disagreement already ;) )

第一次迭代：做明显的 - 读取要复制的列表中的每个节点，并在新的列表中创建的节点。然后，阅读随机节点像这样： this.random.data ，并插入到 LinkedHashSet

First Iteration: Do the obvious - read each node from the list to be copied and create nodes on the new list. Then, read the random node like so: this.random.data and insert into the LinkedHashSet.

第二迭代：遍历该新的列表，并添加每个节点的数据作为第一列和节点本身作为第二塔送入 LinkedHashMap的（不必被链接的，但我只是随大流去）。

Second Iteration: Iterate through the new list and add each node's data as the first column and the node itself as the second column into the LinkedHashMap (doesn't have to be Linked, but I'm just going with the flow).

第三次迭代：迭代 LinkedHashSet （这就是为什么这需要链接的原因 - predictable排序），同时新的列表。对于第一点，看的第一个条目的 LinkedHashSet ，查找相应的对象的的LinkedHashMap 并添加作为随机节点在新的列表中的当前节点。

Third Iteration: Iterate over the LinkedHashSet (this is the reason why this needs to be Linked - predictable ordering) and the new list simultaneously. For the first node, read the first entry of the LinkedHashSet, look up the corresponding object in the LinkedHashMap and add as the random node to the current node in the new list.

3次迭代似乎有点疯狂，但尝试是保持复杂度为O（N）。任何解决方案，提高了对O（3N）的空间要求和O（3N）运行的复杂性将是巨大的。谢谢！

3 iterations does seem a little crazy, but the attempt was to keep the complexity as O(N). Any solution that improves on the O(3N) space requirement and O(3N) runtime complexity would be great. Thanks!

编辑：从入门的 LinkedHashSet 作出进入的LinkedHashMap ，所以这个时候可以去掉会只需要O（2N）的空间。

The entry from the LinkedHashSet can be removed when making an entry into the LinkedHashMap, so this would only take O(2N) space.

推荐答案

作为<一个href="http://stackoverflow.com/questions/5509825/duplicate-a-linkedlist-with-a-pointer-to-a-random-node-apart-from-the-next-node/5509937#5509937">pointed由MahlerFive ，我认为你可以做到这一点为O（2N）运行的复杂性，以及O（N），空间复杂度。

As pointed out by MahlerFive, I think you can do this with O(2N) runtime complexity, and O(N) space complexity.

让我们假设你有

public class Node {
    private Node next;
    private Node random;
    private String data;
    // getters and setters omitted for the sake of brevity
}

我会做的节点的链表深拷贝参考译文：

I would do a deep copy of a linked list of Nodes as:

private Node deepCopy(Node original) {
    // We use the following map to associate newly created instances 
    // of Node with the instances of Node in the original list
    Map<Node, Node> map = new HashMap<Node, Node>();
    // We scan the original list and for each Node x we create a new 
    // Node y whose data is a copy of x's data, then we store the 
    // couple (x,y) in map using x as a key. Note that during this 
    // scan we set y.next and y.random to null: we'll fix them in 
    // the next scan
    Node x = original;
    while (x != null) {
        Node y = new Node();
        y.setData(new String(x.getData()));
        y.setNext(null);
        y.setRandom(null);
        map.put(x, y);
        x = x.getNext();
    }
    // Now for each Node x in the original list we have a copy y 
    // stored in our map. We scan again the original list and 
    // we set the pointers buildings the new list
    x = original;
    while (x != null) {
            // we get the node y corresponding to x from the map
        Node y = map.get(x);
            // let x' = x.next; y' = map.get(x') is the new node 
            // corresponding to x'; so we can set y.next = y'
        y.setNext(map.get(x.getNext()));
            // let x'' = x.random; y'' = map.get(x'') is the new 
            // node corresponding to x''; so we can set y.random = y''
        y.setRandom(map.get(x.getRandom()));
        x = x.getNext();
    }
    // finally we return the head of the new list, that is the Node y
    // in the map corresponding to the Node original
    return map.get(original);
}

---

修改：我发现这个问题是一个重复的问<一href="http://stackoverflow.com/questions/1924741/deep-copy-linkedlist-without-destroying-original-list-and-extra-storage-space-us">here:还有你找到一个<一个href="http://stackoverflow.com/questions/1924741/deep-copy-linkedlist-without-destroying-original-list-and-extra-storage-space-us/1924968#1924968">answer它展示了如何解决O（3N）运行的复杂性这个问题，没有多余的空间：很巧妙！但它使用与C指针一招，我不知道如何用Java做同样的。

---

Edit: I found that this question is a duplicate of the one asked here: there you find an answer that shows how to solve this problem in O(3N) runtime complexity with no extra space: very ingenious! But it uses a trick with C pointers, and I'm not sure how to do the same in java.

这篇关于从下一个节点重复使用指针在LinkedList到随机节点相距的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！