golang 解法, 执行用时: 0 ms, 内存消耗: 3.5 MB, 提交时间: 2022-11-13 11:30:24

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
 
/*
本题要求我们对一个特殊的链表进行深拷贝。
如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。
而本题中因为随机指针的存在，当我们拷贝节点时，
「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。
一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。
对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，
拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。
遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。
如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。
当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。
注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，
为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，
如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

在实际代码中，我们需要特别判断给定节点为空节点的情况。

*/

var cachedNode map[*Node]*Node

func deepCopy(node *Node) *Node {
    if node == nil {
        return nil
    }
    if n, has := cachedNode[node]; has {
        return n
    }
    newNode := &Node{Val: node.Val}
    cachedNode[node] = newNode
    newNode.Next = deepCopy(node.Next)
    newNode.Random = deepCopy(node.Random)
    return newNode
}

func copyRandomList(head *Node) *Node {
    cachedNode = map[*Node]*Node{}
    return deepCopy(head)
}

golang 解法, 执行用时: 0 ms, 内存消耗: 3.3 MB, 提交时间: 2022-11-13 11:29:56

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
 
/*
我们首先将该链表中每一个节点拆分为两个相连的节点，
例如对于链表 A→B→C，我们可以将其拆分 A→A′→B→B′→C→C′。 
对于任意一个原节点 S，其拷贝节点 S' 即为其后继节点。
这样，我们可以直接找到每一个拷贝节点 S' 的随机指针应当指向的节点，
即为其原节点 S 的随机指针指向的节点 T 的后继节点 T' 。
需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。
同样需要注意最后一个拷贝节点的后继节点为空，我们需要特别判断这种情况。

*/

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    for node := head; node != nil; node = node.Next.Next {
        node.Next = &Node{Val: node.Val, Next: node.Next}
    }
    for node := head; node != nil; node = node.Next.Next {
        if node.Random != nil {
            node.Next.Random = node.Random.Next
        }
    }
    headNew := head.Next
    for node := head; node != nil; node = node.Next {
        nodeNew := node.Next
        node.Next = node.Next.Next
        if nodeNew.Next != nil {
            nodeNew.Next = nodeNew.Next.Next
        }
    }
    return headNew
}