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 representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif 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:
代码语言：javascript复制Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.Constraints:
0 <= n <= 1000-10000 <= Node.val <= 10000Node.randomisnullor is pointing to some node in the linked list.
思路：
题目意思是深拷贝一个单链表，但是链表节点的有一个random指针，指向任意一个节点或者nil。 难点在于random指针的拷贝，最直接的办法就是用一个map，保存新旧节点的对应关系，然后再赋值random和next的关系，因为通过mapping关系，就能找到新节点应该的next和random应该指向谁。 这种做法无疑引入了一个map，增加了空间复杂度。可以考虑将拷贝的节点，放置到单链表的被拷贝节点的后一位，这样就可以省掉map来存这个新旧节点的对应关系。最后把单链表拆开就行。
代码：
golang：
代码语言：javascript复制/**
* 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
}
}
