剑指Offer 35. 复杂链表的复制

题目链接： 剑指Offer 35. 复杂链表的复制

题目描述：

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解法思路：

1. 遍历整个链表，在每个节点的后面，插入一个当前节点的复制，使得 1->2->3 变成 1->1->2->2->3->3

2. 遍历整个链表，将原节点的random指针也复制到后面的节点上，即 :p.Random.Next = p.Next.Random

3. 使用一个虚拟节点，将所有复制出来的节点串联在一起，得到原链表的复制
   代码：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    p1,p2,p3:= head,head,head
    //1.
    for p1 != nil{
        tmp := &Node{ Val: p1.Val, Next: p1.Next, Random: nil }
        p1.Next = tmp
        p1 = p1.Next.Next
    }

    for p2 != nil {
        if p2.Random != nil {
            p2.Next.Random = p2.Random.Next
        }
        p2 = p2.Next.Next
    }
    // 3.
    dummy := head.Next
    tmp := dummy
    for p3 != nil {
        p3.Next = p3.Next.Next
        if p3.Next != nil { tmp.Next = p3.Next.Next }
        p3, tmp = p3.Next, tmp.Next
    }

    return dummy

}