ac solution code

  • 0

    The generic solution for Clone Graph:

    1. Clone nodes
    2. Clone neighbors

    This question is similar as Clone Graph. The basic idea is pretty straight forward: travel from the head to the tail of the old linkedList, deep copying corresponding new nodes. The only trick is using a HashMap to save the pairing relationship between oldNode and newNode, so that we can get the corresponding pointer to the node's 'random' variable in the new list.

    class CopyListwithRandomPointer: LeetcodeProtocol {
        func copyRandomList(head: RandomListNode) -> RandomListNode {
            var head: RandomListNode? = head
            var map = [RandomListNode: RandomListNode]()// map: [oldNode: newNode]
            var node: RandomListNode? = RandomListNode(head!.label)
            map[head!] = node
            let res = node!
            let oldHead = head
            while head?.next != nil {           // 1-1. Traversal: head -> tail
                node!.next = RandomListNode(head!.next!.label)
                map[head!.next!] = node!.next   // 1-2. map[oldNode] = newNode
                head = head!.next!
                node = node!.next!
            // Copy random of new nodes from map
            head = oldHead
            node = res
            while head != nil {// 2. Clone neighbors: clone `random` from map
                if let oldRandom = head!.random {
                    node?.random = map[oldRandom]
                node = node!.next
                head = head!.next
            return res

    0_1485821366112_Evernote Camera Roll 20170130 160511.jpg

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.