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

1. 问题描述

2. 思路

2.1. 思路一

1. 将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A ′ →B→B ′ →C→C ′
2. 我们可以直接找到每一个拷贝节点 S ′ 的随机指针应当指向的节点，即为其原节点 SS 的随机指针指向的节点 T的后继节点 T ′
3. 将重装好的链表进行拆分

2.2. 思路二

1. 声明一个map[*Node]*Node类型的map
2. 遍历链表，以node为key，当前node的值为Value重构一个node
3. 再次遍历链表，将map中的value，重新构造

3. 代码

3.1. 思路一代码

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

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    for cur := head; cur != nil; cur = cur.Next.Next {
        cur.Next = &Node {
            Val : cur.Val,
            Next : cur.Next,
        }
    }

    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next 
        }
    }

    head1 := head.Next
    for cur := head; cur != nil; cur = cur.Next {
        cur1 := cur.Next
        // cur和cur1将一个链表拆分成两个链表
        cur.Next = cur.Next.Next
        if cur1.Next != nil {
            cur1.Next = cur1.Next.Next
        }
    }
    return head1
}

3.2. 思路二代码

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    cur := head
    nodes := map[*Node]*Node{}
    for cur != nil {
        nodes[cur] = &Node{
            Val:cur.Val,
        }
        cur = cur.Next
    }

    cur = head
    for cur != nil {
        nodes[cur].Next = nodes[cur.Next]
        nodes[cur].Random = nodes[cur.Random]
        cur = cur.Next
    }
    return nodes[head]
}