使用指向除下一节点之外的随机节点的指针复制LinkedList

Question

问:链表的每个节点都有一个随机指针(除了下一个指针),它可以随机指向另一个节点或为空.你会如何复制这样的链表？

答:这就是我所拥有的,我只是想批准这是否是最佳方式.

由于没有指定空间限制,我将使用a LinkedHashSet和a LinkedHashMap(我可以想象人们已经在分歧中点头;))

第一次迭代:显而易见 - 从列表中读取每个节点以进行复制并在新列表上创建节点.然后,像这样读取随机节点:this.random.data并插入到LinkedHashSet.

第二次迭代:遍历新列表并将每个节点的数据添加为第一列,将节点本身作为第二列添加到LinkedHashMap(不必是链接,但我只是使用流程).

第三次迭代:迭代LinkedHashSet(这就是为什么需要链接 - 可预测的排序)和新列表同时进行.对于第一个节点,读取其中的第一个条目,在其中LinkedHashSet查找相应的对象LinkedHashMap,并将其作为随机节点添加到新列表中的当前节点.

3次迭代似乎有点疯狂,但尝试将复杂性保持为O(N).任何改进O(3N)空间要求和O(3N)运行时复杂性的解决方案都会很棒.谢谢!

---

编辑:进入LinkedHashSet时可以删除该条目LinkedHashMap,因此这只需要O(2N)空间.

Answer 1

正如MahlerFive所指出的,我认为你可以用O(2N)运行时复杂度和O(N)空间复杂度来做到这一点.

我们假设你有

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

我会做一个Nodes 链表的深层副本:

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);
}

编辑:我发现这个问题是一个重复的问在这里:你有找到一个答案,说明如何为O解决这个问题(3N)运行的复杂性,没有多余的空间:很巧妙!但它使用C指针的技巧,我不知道如何在java中做同样的事情.