Copy List with Random node

class Node : Hashable{
    var next : Node?
    var random : Node?
    var key : String
    init(_ str: String) {
        self.key = str
    }
    static func == (ls: Node, rs: Node) -> Bool{
        return ls.key == rs.key
    }
    func hash(into hasher: inout Hasher) {

    }
}


var map = [Node: Node]() //orignal - copied

func copyListWithRandom(_ node: Node?) -> Node?{
    guard let node = node else {
        return nil
    }
    let copyHeader = Node(node.key)
    map[node] = copyHeader

    var runner : Node? = node

    while runner != nil{
        let curr = runner!
        let new = getNewNode(curr)!
        new.next =  getNewNode(curr.next)
        new.random = getNewNode(curr.random)
        runner = curr.next
    }
    return getNewNode(node)
}

func getNewNode(_ old : Node?) -> Node?{
    guard let old = old else { return nil }
    if let node = map[old]{
        return node
    }
    let node = Node(old.key)
    map[old] = node
    return node
}




let n1 = Node("a")

let n2 = Node("b")
let n3 = Node("c")
let n4 = Node("d")

n1.next = n2
n2.next = n3
n3.next = n4
n4.random = n1
n1.random = n3


func printNode(_ node: Node?){
    var n = node
    while n != nil {
        print(n!.key)
        if let random = n!.random{
            print("  random: \(random.key)")
        }
        n = n!.next
    }
}

print("BEFORE ---------")
printNode(n1)

let copy = copyListWithRandom(n1)
print("")
print("")
print("COPY ---------")
printNode(copy)