问题描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
**
示例 1：
image.png
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
image.png
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

问题分析

对于一个简单链表来说，如果我们需要复制的话，需要把每个节点都进行复制然后逐个的链接起来，这样看起来就比较的简单，代码实现如下：

  1. public Node copy(Node head){
  2.     if(head == null){
  3.         return null;
  4.     }
  5.     Node cur = head.next;
  6.     Node newHead = new Node(head.val);
  7.     Node curNew = newHead;
  8.     while(cur != null){
  9.         Node node = new Node(cur.val);
  10.         curNew.next = node;
  11.         curNew = node;
  12.         cur = cur.next;
  13.     }
  14.     return newHead;
  15. }

但是这里涉及一个问题，就是还存在一个随机的节点指针指向的节点是随机的，这个需要我们处理，那么怎么才能够完成了，上面的代码逻辑是逐个创建并链接到一起的，但是随机节点不一定创建出来了，针对这个问题我们可能把创建好的新节点链接在已有的节点后面，然后再逐个遍历新节点的随机节点就是前面节点对应随机节点的下一个节点，最后将copy的新节点从原先的链表中提取出来；

  1. 复制新节点，并放在原有节点的后面；
  2. 遍历节点，并复制新节点的随机节点，该节点为原有节点的随机节点的下一个节点；
  3. 提取复制节点列表，保持原有列表不变；

代码实现

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         if(head == null){
  4.             return head;
  5.         }
  6.         Node cur = head;
  7.         while(cur != null){
  8.             Node newNode = new Node(cur.val);
  9.             newNode.next = cur.next;
  10.             cur.next = newNode;
  11.             cur = newNode.next;
  12.         }
  13.         cur = head;
  14.         //copy random
  15.         while(cur != null && cur.next != null){
  16.             if(cur.random != null){
  17.                 cur.next.random = cur.random.next;
  18.             }
  19.             cur = cur.next.next;
  20.         }
  21.         Node newHead = head.next;
  22.         Node copy = newHead;
  23.         head.next = head.next.next;
  24.         if(copy.next != null){
  25.             cur = copy.next;
  26.         }
  27.         while(cur != null && cur.next != null){
  28.             copy.next = cur.next;
  29.             cur.next = cur.next.next;
  30.             copy = copy.next;
  31.             if(copy != null){
  32.                 cur = copy.next;
  33.             }
  34.         }
  35.         return newHead;
  36.     }
  37. }