138. 复制带随机指针的链表

138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

解题思路

此处撰写解题思路
借助map 俩次遍历
第一次 克隆节点
第二次 链接节点

func copyRandomList(head *Node) *Node {
    m := make(map[*Node]*Node)
    cur := head
    for (cur != nil) {
        temp := &Node{cur.Val, nil, nil}
        m[cur] = temp
        cur = cur.Next
    }
    cur = head
    for (cur != nil) {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
        cur = cur.Next
    }
    return m[head]
}

方法一：很有意思，利用哈希表建链表。
因为链表不需要顺序，只要知道head，后面都是通过指针连接的。
先建结构，再连指针。
m[p].Next = m[p.Next] 与 p.Next = next 是一样的用法，在map里面，可以直接拿到p.Next

func copyRandomList(head *Node) *Node {
     m := make(map[*Node]*Node)              //定义一个哈希表
    for p := head; p != nil ; p = p.Next {  //1,克隆节点
        m[p] = &Node{p.Val,nil,nil}
    }
    for p := head; p != nil ; p = p.Next {  //2,链接节点
        m[p].Next = m[p.Next]       //p.Next = next 是一样的用法
        m[p].Random = m[p.Random]
    }
    return m[head]
}

方法二：解题思路，在原链表后，指向新链表1->1’->2->2’

首先明白深拷贝和浅拷贝的区别：
浅拷贝就是说你在拷贝一种数据结构的时候，如果拷贝的只是这个结构的引用，呢这就是浅拷贝。也即是说浅拷贝出来的结果和原数据结构的引用都是指向同一个内存地址
而深拷贝就是要把内存指向的地址中的数据提取出来。
1、创建一个新的listNode来拷贝每一个节点，而不是通过引用，这里就是深拷贝了。然后链接（这一步只处理了Val和Next两个字段）
1->1’->2->2’
2、第一步并没有处理Random字段，需要在这一步处理。
这一步里将拷贝节点的Random指向和原节点相同的Random节点
3、就是将原节点和拷贝节点分离开来。这里就是要把拷贝节点的Next指针指向与原节点的Next指针相同的位置，
返回克隆链表 o1，o1

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    // 复制节点，紧挨到到后面
    // 1->2->3  ==>  1->1'->2->2'->3->3'
    cur := head
    for cur != nil {
        clone := &Node{Val: cur.Val, Next: cur.Next}
        temp := cur.Next
        cur.Next = clone
        cur = temp
    }
    // 处理random指针
    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }
    // 分离两个链表
    //处理next指针
    cur = head
    cloneHead := cur.Next
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }

    // 原始链表头：head 1->2->3
    // 克隆的链表头：cloneHead 1'->2'->3'
    return cloneHead
}