题解 | #复杂链表的复制#

package main

/*
type RandomListNode struct {
    Label int
    Next *RandomListNode
    Random *RandomListNode
}
*/

/**
 *
 * @param pHead RandomListNode类
 * @return RandomListNode类
*/
func Clone( head *RandomListNode ) *RandomListNode {
    //write your code here
    // 0. 特殊条件判断
    if head == nil {
        return nil
    }
    // 1. 一边遍历创建一个新的链表，一边保存新节点与旧节点的映射
    // 2. 再次遍历，将新节点的 random 指针连接到与旧节点映射的新节点上
    head1 := head
    newHead := &RandomListNode{Label: head1.Label}
    head2 := newHead

    m := map[*RandomListNode]*RandomListNode{}
    m[head1] = head2

    // 创建新链表，链接 next
    for head1.Next != nil {
        head2.Next = &RandomListNode{Label: head1.Next.Label}
        head1 = head1.Next
        head2 = head2.Next
        m[head1] = head2
    }

    // 链接 random
    head1, head2 = head, newHead
    for head1 != nil {
        head2.Random = m[head1.Random]
        head1 = head1.Next
        head2 = head2.Next
    }

    return newHead
}