138. Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

Constraints:

• 0 <= n <= 1000
• -10000 <= Node.val <= 10000
• Node.random is null or is pointing to some node in the linked list.

思路：

题目意思是深拷贝一个单链表，但是链表节点的有一个random指针，指向任意一个节点或者nil。
难点在于random指针的拷贝，最直接的办法就是用一个map，保存新旧节点的对应关系，然后再赋值random和next的关系，因为通过mapping关系，就能找到新节点应该的next和random应该指向谁。
这种做法无疑引入了一个map，增加了空间复杂度。可以考虑将拷贝的节点，放置到单链表的被拷贝节点的后一位，这样就可以省掉map来存这个新旧节点的对应关系。最后把单链表拆开就行。

代码：

golang：

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

func copyRandomList1(head *Node) *Node {
    if head == nil {
        return head
    }
    
    // build newList
    var mapping = make(map[*Node]*Node, 0)
    for temp:= head; temp != nil; temp = temp.Next{
        mapping[temp] = &Node{Val: temp.Val}
        
    }
    
    // 拷贝next指针和random指针关系
    for temp:= head; temp != nil; temp = temp.Next {
        mapping[temp].Next = mapping[temp.Next]
        mapping[temp].Random = mapping[temp.Random]
    }
    
    return mapping[head]
}

// O(1) 空间的迭代
func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    
    // 1. 把复制的节点都放在被复制的节点后
    for temp:= head; temp != nil; {
        newNode := &Node{Val:temp.Val, Next: temp.Next}
        temp.Next = newNode
        temp = newNode.Next
    }
    
    // 2. 复制random指针关系
    for temp:= head; temp != nil; temp = temp.Next.Next {
        if temp.Random != nil {
            // 因为 next节点保存的都是新节点，随机指针指向的下一个节点肯定也是新链表的下一个节点
            temp.Next.Random = temp.Random.Next 
        }
    }
    // 3. 和拆分奇偶链表一样拆开单链表就行
    var (
        newList = head.Next
        odd = head
        even = head.Next
    )
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next // 实际上是even
        
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = nil // 抹掉odd链上最后一个节点的next
    
    return newList
}

func printList(head *Node) {
    node := head
    for node != nil {
        fmt.Printf("%d, ", node.Val)
        node = node.Next
    }
}