0138. Copy List With Random Pointer

# 138. Copy List with Random Pointer#

## 题目 #

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

Return a  deep copy of the 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`) where random pointer points to, or `null` if it does not point to any node.

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: Given linked list is empty (null pointer), so return null.

``````

Constraints:

• `10000 <= Node.val <= 10000`
• `Node.random` is null or pointing to a node in the linked list.
• The number of nodes will not exceed 1000.

## 题目大意 #

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

## 解题思路 #

• 这道题严格意义上是数据结构题，根据给定的数据结构，对它进行深拷贝。

• 先将每个节点都复制一份，放在它的 next 节点中。如此穿插的复制一份链表。

再将穿插版的链表的 random 指针指向正确的位置。

再将穿插版的链表的 next 指针指向正确的位置。最后分开这交织在一起的两个链表的头节点，即可分开 2 个链表。

## 代码 #

``````package leetcode

// Node define
type Node struct {
Val    int
Next   *Node
Random *Node
}

return nil
}
}

for cur != nil && cur.Next != nil {
cur.Next, cur = cur.Next.Next, cur.Next
}
}

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