复杂链表的复制

---

题目：

题解：

​ 本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。

1、回溯 + 哈希表

• 解题思路：

  • 一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

• 复杂度分析：

  • 时间复杂度：O(n)，其中 n 是链表的长度。对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。
  • 空间复杂度：O(n)，其中 n 是链表的长度。为哈希表的空间开销。

• 代码：

  // 回溯 + 哈希表
  class Solution2 {
      Map<Node, Node> cachedNode = new HashMap<Node, Node>();
  
      public Node copyRandomList(Node head) {
          if (head == null) {
              return null;
          }
          if (!cachedNode.containsKey(head)) {
              Node headNew = new Node(head.val);
              cachedNode.put(head, headNew);
              headNew.next = copyRandomList(head.next);
              headNew.random = copyRandomList(head.random);
          }
          return cachedNode.get(head);
      }
  }

2、迭代 + 节点拆分（方法很nice）

• 解题思路：

  • 
  • 
  • 
  • 
  • 

• 复杂度分析：

  • 时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。
  • 空间复杂度：O(1)。注意返回值不计入空间复杂度

• 代码：

  class Solution {
      public Node copyRandomList(Node head) {
          if (head == null) {
              return head;
          }
          // 完成链表节点的复制
          for (Node cur = head; cur != null; cur = cur.next.next) {
              Node newNode = new Node(cur.val);
              newNode.next = cur.next;
              cur.next = newNode;
          }
  
          // 完成链表复制节点的随机指针复制
          for (Node cur = head;cur != null; cur = cur.next.next) {
              Node newNode = cur.next;
              newNode.random = (cur.random != null)?cur.random.next:null; // cur.random为空，空节点不能.next，否则会报错
          }
          Node headNew = head.next;
          // 将链表一分为二
          for (Node cur = head; cur != null; cur = cur.next) {
              Node newNode = cur.next;
              cur.next = newNode.next;
              newNode.next = (cur.next != null)? cur.next.next:null; // 这里判断同理
          }
  
          return headNew;
      }
  }