复杂链表的复制

1. 题目描述

请实现函数ComplexListNode *Clone（ComplexListNode* pHead），复制一个复杂链表。在复杂链表中，每个结点除了有一个 next 指针指向下一个结点外，还有一个 sibling 指向链表中的任意结点或者 NULL。

2. 思路分析

按照正常的思路，首先从头到尾遍历链表，拷贝每个节点的 value 和 next 指针。然后从头再次遍历，第二次遍历的目的在于拷贝每个节点的 sibling 指针。

然而即使找到原节点的 sibling 指针，还是得为了找到复制节点对应的 sibling 指针而再遍历一遍。那么对于 n 个要寻找 sibling 指针的节点，复杂度就是 O(N*N)。

显然，为了降低复杂度，必须从第二次遍历着手。这里采用的方法是，在第一次遍历的时候，把 (原节点, 复制节点) 作为映射保存在表中。那么第二次遍历的时候，就能在 O(1) 的复杂度下立即找到原链上 sibling 指针在复制链上对应的映射。

3. 代码分析

class Node {
  constructor(value, next = null, sibling = null) {
    this.value = value;
    this.next = next;
    this.sibling = sibling;
  }
}

/**
 * 复制复杂链表
 * @param {Node} first
 */
function cloneNodes(first) {
  if (!first) {
    return null;
  }

  const map = new Map();

  let copyFirst = new Node(first.value),
    node = first.next, // 被copy链的当前节点
    last = copyFirst; // copy链的当前节点, 此节点相对于被copy链短位移少1位

  map.set(first, copyFirst);

  while (node) {
    last.next = new Node(node.value);
    last = last.next;
    map.set(node, last);
    node = node.next;
  }

  // 第二次遍历, 迁移sibling
  node = first;
  while (node) {
    map.get(node) && (map.get(node).sibling = map.get(node.sibling));
    node = node.next;
  }

  return copyFirst;
}

/**
 * 测试代码
 */
const node1 = new Node("a"),
  node2 = new Node("b"),
  node3 = new Node("c"),
  node4 = new Node("d");

node1.next = node2;
node2.next = node3;
node3.next = node4;

node1.sibling = node3;
node4.sibling = node2;

let copyNode = cloneNodes(node1);
while (copyNode) {
  console.log(copyNode);
  copyNode = copyNode.next;
}

大师兄

1. 题目描述

2. 思路分析

3. 代码分析