题目

复制带随机指针的链表

问题:

给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。返回一个深拷贝的链表。

说明:

可否使用O(1)的空间

示例:

解题思路:

哈希表解法的思路：
第一步，将原链表从头遍历，然后将每个节点深拷贝一份(这里的深拷贝意思：创建一个新的节点，里面的值用原节点的值一样)，然后将这个新的节点放入哈希表中，其中key为原节点，value为新的节点；
第二步，从头再遍历原链表，每次遍历从哈希表中取以当前节点为key的新节点，获得新的节点之后，新的节点的next为当前节点的next为key的新节点，新的节点的random也是如此。

代码：

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}

extension SingNode : CustomStringConvertible {
    public var description: String {
        var string = "\(value)"
        var node = self.nextNode
        
        while node != nil {
            string = string + " -- " + "\(node!.value)"
            node = node?.nextNode
        }
        return string
    }
}
 **/
      
    func randomListNode(_ l1 : SingNode?) -> SingNode? {
        var dictionary = Dictionary<SingNode,SingNode>()
        var p = l1
        while p != nil {
            let newNode = SingNode.init(value: p!.value)
            dictionary.updateValue(newNode, forKey:p!)
            p = p?.nextNode
        }
        
        p = l1
        
        while p != nil {
            let q:SingNode = dictionary[p!]!
            if p!.nextNode != nil {
                q.nextNode = dictionary[p!.nextNode!]
            } else {
                q.nextNode = nil
            }
            p = p?.nextNode
        }
        return dictionary.removeValue(forKey: l1!)
    }