复杂链表的复制

题目

实现复制一个复杂链表的函数。在链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中任意节点或者null。

示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

分析

但看这个输入输出，我们可以发现，这看上去是一个二维数组。其中作为元素项的数组组成如[节点的值, 随机指向的节点的序号]，在基础的链表上添加了一个随机指向的指针，指向链表中某一个节点的序号或null。

复制复杂链表解决的问题其实就是random属性的处理，我们到底是要在创建链表时就添加random还是创建完链表再次遍历添加random。

原地复制再拆分

思路是在原来的链表节点后复制一个新节点，然后再添加指向，最后再将新建的节点拆分出来。

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {

  if (!head) return null
  
  for(let node = head, copy = null; node; node = node.next.next) {
    // 遍历新建节点，先复制node节点的值在复制next，最后接到node后边
    copy = new Node(node.val)
  	copy.next = node.next
  	node.next = copy
  }
	for(let node = head; node; node = node.next.next) {
    // 添加random，node复制出来的random应该指向node.random的复制
    if(node.random) {
      node.next.random = node.random.next
    }
  }
  let newHead = head.next
  for(let node = head, temp = null; node && node.next;) {
    // 
    temp = node.next
    node.next = temp.next
    node = temp
  }
	return newHead
};

算法过程图解：

遍历一遍链表，在每个节点后生成新的节点，时间复杂度为O(n)，添加random时，链表长度翻倍，时间复杂度为O(2n)，拆分链表时又遍历一次长链表，时间复杂度为O(2n)，所以总的时间复杂度应该为O(5n)。

新建一个链表，再加几个临时变量，空间复杂度大约为O(n)。

使用Map

将所有的节点存放到Map中，生成node => newNode的映射，然后再迭代生成新链表。

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
  if(!head) return null
  let node = head, list = new Map()
  while(node) {
    list.set(node, new Node(node.val))
    node = node.next
  }
  let newNode = head
  while(newNode) {
    list.get(newNode).next = newNode.next ? list.get(newNode.next) : null
    list.get(newNode).random = newNode.random ? list.get(newNode.random) : null
    newNode = newNode.next
  }
  
  return list.get(head)
}

遍历链表一次生成map，再遍历一次map生成链表，时间复杂度O(2n)，比原地复制少一点。

但是在空间复杂度上，由于多创建了一个map，空间复杂度为O(2n)，比第一种方法略多。