Это небольшое улучшение по сравнению с ответом @ephemient, который не использует дополнительный указатель what. Вот эскиз реализации в 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 i.e. A'.next and A'.data points to C
newNode.next = orig.data
// The data pointer on orig node points to the cloned node. i.e. 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
// (i.e. it still points to B') while A'.next is being set
clone.next = if (orig.next == null) null else orig.next.data
}
cloneHead
}