深层复制Linkedlist而不破坏原始列表和额外的存储空间(使用ANSI C)

这个链表与普通链表不同的是,除了下一个指针外,它还有另一个指针,指向链表中除了它自己之外的另一个节点。

那么深刻复制这个链表没有破坏原始而没有额外空间的最佳方法是什么?

我的方法只是做一个O(n ^ 2)循环,但应该是一些更聪明的方法。

这个实现是完全未经测试的,但这个想法非常简单。

#include  struct node { struct node *next; struct node *what; void *data; }; struct node *copy(struct node *root) { struct node *i, *j, *new_root = NULL; for (i = root, j = NULL; i; j = i, i = i->next) { struct node *new_node = malloc(sizeof(struct node)); if (!new_node) abort(); if (j) j->next = new_node; else new_root = new_node; new_node->data = i->data; i->data = new_node; } if (j) j->next = NULL; for (i = root, j = new_root; i; i = i->next, j = j->next) j->what = i->what->data; for (i = root, j = new_root; i; i = i->next, j = j->next) i->data = j->data; return new_root; } 
  1. 在原始列表中接下来->next ,创建一个镜像它的新列表。 Mangle ->data旧列表中每个节点上的->data ,指向新列表中的相应节点。
  2. 并行浏览两个列表并使用早期的mangled ->data来确定->what新列表中的内容。
  3. 并行浏览两个列表并将->data恢复到原始状态。

请注意,这是3次线性传递,因此它的时间是O(n),并且它不使用超出创建新列表所需的任何内存。

这是一个经过测试的ephemient解决方案的C ++实现,它使用下一个指针在第一次传递中交错节点,而不是为此暂时接管数据。 复杂性和空间使用保持相同(O(N)(3遍)和O(1)空间)作为ephemients实现

 struct Link { int data; shared_ptr next; weak_ptr random; }; shared_ptr DeepCopy(Link* original) { if (!original) return nullptr; // 1st Pass: // make new nodes and interleave them between the nodes of the original list // by changing the next pointers ie: // [1]->[copy of 1]->[2]->[copy of 2]->[3]->[copy of 3] .... // during this pass, we will also set the data of new nodes to match the old node // being copied. Link* node = original; while (node) { shared_ptr new_node = make_shared(); new_node->data = node->data; new_node->next = node->next; node->next = new_node; node = node->next->next.get(); // skipping the "copy of" node just inserted } // 2nd Pass: // now go through and set the random ptr of the new nodes correctly. // i refers to a node on the original list and j the matching node on the new // list shared_ptr new_head = original->next; // ie "copy of 1" is head of new list for (Link *i = original; i; i=i->next->next.get()) { Link *j = i->next.get(); // new nodes interleave original nodes j->random = i->random.lock()->next; } // 3rd Pass: // Restore the original list Link* new_node = new_head.get(); node = original; while (node) { node->next = new_node->next; if (node->next) new_node->next = node->next->next; node = node->next.get(); new_node = new_node->next.get(); } return new_head; } 

您可以在每个节点上分支搜索,并在遇到已访问过的节点时将路径重新合并。

这是@ephemient给出的答案的一个小改进,它不使用额外的指针。 这是Scala中实现的草图。 评论假定如下列表:

 +-----------+ | | | v A --> B --> C----+ ^ | ^ | | | | | +-----+ +----+ 

Node如:

 class Node { var data: Node = null var next: Node = null def traverse(fn: Node => Unit) { var node = this while (node != null) { fn(node) node = node.next } } } 

这里是克隆方法。

 def clone(list: Node): Node = { if (list == null) return null var cloneHead: Node = null // first, create n cloned nodes by traversing the original list in O(n) time // this step mutates the data pointers of original list list traverse { orig => // for each node in original list, create a corresponding cloned node val newNode = new Node if (orig == list) { cloneHead = newNode // store the head node of the cloned list } // The next pointer of cloned node points to the node pointed to by // the corresponding orig node's data pointer ie A'.next and A'.data points to C newNode.next = orig.data // The data pointer on orig node points to the cloned node. ie A.data points to A' orig.data = newNode } // then, fix up the data pointers of cloned list by traversing the original // list in O(n) time list traverse { orig => clone = orig.data // since the data pointer on orig node points to // the corresponding cloned node // A'.next points to C and C.data points to C', so this sets A'.data to C' // this establishes the data pointers of the cloned nodes correctly clone.data = if (clone.next == null) null else clone.next.data } // then, fix up the data pointers of original list and next pointers of cloned list // by traversing the original list in O(n) time list traverse { orig => clone = orig.data // since the data pointer on orig node still // points to the corresponding cloned node // A.data points to A' and A'.next points to C, so this sets A.data to C, // restoring the original list orig.data = if (orig.data == null) null else orig.data.next // A.next points to B and B.data points to B', so this sets A'.next to B' // since we are working on linked list's next pointers, we don't have to worry // about back pointers - A will be handled by this traversal before B, // so we know for sure that that B.data is not "fixed" yet // (ie it still points to B') while A'.next is being set clone.next = if (orig.next == null) null else orig.next.data } cloneHead } 

这里是带有随机指针的链表深度副本的c#版本:时间复杂度是带有常量空间的O(N)(即只用于创建深层复制的空间)(注意同样可以通过添加O(n)的映射来实现空间)

(您可以参考我的博客: http : //codingworkout.blogspot.com/2014/07/deep-copy-with-random-pointer.html )更改的要点:

  1. 在第一次迭代中,创建给定原始列表的副本,使原始节点指向副本
  2. 在第二次迭代中,更新复制列表的随机指针
  3. 分开他们

    public LinkedListWithRandomPointerNode DeepCopy(){if(this._first == null){return null; }

      LinkedListWithRandomPointerNode i1 = this._first, i2 = null; while(i1 != null) { //cre new node i2 = new LinkedListWithRandomPointerNode(); i2.e = i1.e; i2.next = i1.next; //insert it after i1 i1.next = i2; i1 = i2.next; } LinkedListWithRandomPointerNode firstNodeOfCopiedList = this._first.next; i1 = this._first; i2 = i1.next; while(i2 != null) { if(i1.random != null) { i2.random = i1.random.next; } if(i2.next == null) { break; } i1 = i2.next; i2 = i1.next; } i1 = this._first; i2 = i1.next; while (i2 != null) { i1.next = i2.next; i1 = i1.next; if (i1 != null) { i2.next = i1.next; i2 = i2.next; } else { i2.next = null; break; } } return firstNodeOfCopiedList; } 

哪里

 public class LinkedListWithRandomPointerNode { public int e; public LinkedListWithRandomPointerNode next; public LinkedListWithRandomPointerNode random; } 

unit testing

 [TestMethod] public void LinkedListWithRandomPointerTests() { var n = this.DeepCopy(); Assert.IsNotNull(n); var i1 = this._first; var i2 = n; while(i1 != null) { Assert.IsNotNull(i2); Assert.IsTrue(i1.e == i2.e); if(i1.random != null) { Assert.IsNotNull(i2.random); Assert.IsTrue(i1.random.e == i2.random.e); } i1 = i1.next; i2 = i2.next; } } LinkedListWithRandomPointerNode _first = null; public LinkedListWithRandomPointer() { this._first = new LinkedListWithRandomPointerNode() { e = 7 }; this._first.next = new LinkedListWithRandomPointerNode() { e = 14 }; this._first.next.next = new LinkedListWithRandomPointerNode() { e = 21 }; this._first.random = this._first.next.next; this._first.next.next.random = this._first; }