Leetcode#138 Copy List with Random Pointer

原题地址

非常巧妙的方法，不需要用map，只需要O(1)的额外存储空间，分为3步：

1. 先复制链表，但是这个复制比较特殊，每个新复制的节点添加在原节点的后面，相当于"加塞"
2. 根据原节点的 ramdon 指针构造新节点的 random 指针
3. 恢复原链表结构，同时得到新复制链表

时间复杂度：O(n)

注意random有可能是NULL

代码：

RandomListNode *copyRandomList(RandomListNode *head) {
  RandomListNode *h = NULL;

  h = head;
  while (h) {
    RandomListNode *node = new RandomListNode(h->label);
    node->next = h->next;
    h->next = node;
    h = h->next->next;
  }

  h = head;
  while (h) {
    h->next->random = h->random? h->random->next : NULL;
    h = h->next->next;
  }

  h = head? head->next : NULL;
  while (head) {
    RandomListNode *tmp = head->next;
    head->next = head->next->next;
    tmp->next = head->next ? head->next->next : NULL;
    head = head->next;
  }

  return h;
}