📑 题目：138. 复制带随机指针的链表

🚀 本题 LeetCode 传送门

题目大意

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• 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
}
func copyRandomList(head *Node) *Node {
 if head == nil {
  return nil
 }
 tempHead := copyNodeToLinkedList(head)
 return splitLinkedList(tempHead)
}
func splitLinkedList(head *Node) *Node {
 cur := head
 head = head.Next
 for cur != nil && cur.Next != nil {
  cur.Next, cur = cur.Next.Next, cur.Next
 }
 return head
}
func copyNodeToLinkedList(head *Node) *Node {
 cur := head
 for cur != nil {
  node := &Node{
   Val:  cur.Val,
   Next: cur.Next,
  }
  cur.Next, cur = node, cur.Next
 }
 cur = head
 for cur != nil {
  if cur.Random != nil {
   cur.Next.Random = cur.Random.Next
  }
  cur = cur.Next.Next
 }
 return head
}

**