【ACWing】48. 复杂链表的复刻

https://www.acwing.com/problem/content/89/

请实现一个函数可以复制一个复杂链表。在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：函数结束后原链表要与输入时保持一致。

数据范围：
链表长度 [ 0 , 500 ] [0,500] [0,500]。

先将原链表的每个节点之后都拷贝出一个新节点，比如原先是 1 → 2 → . . . 1to 2to ... 1→2→...，那么现在就是 1 → 1 ′ → 2 → 2 ′ → . . . 1to 1'to 2to 2'to ... 1→1′→2→2′→...，然后把对应的random指针赋值，最后把新拷贝的链表隔离出来，原链表恢复原状。代码如下：

struct ListNode {
  int val;
  ListNode *next, *random;
  ListNode(int x) : val(x), next(NULL), random(NULL) {}
};

class Solution {
public:
  ListNode *copyRandomList(ListNode *head) {
    ListNode *dummy = new ListNode(0), *prev = dummy;
    ListNode *tmp = head;
    while (tmp) {
      ListNode *node = new ListNode(tmp->val);
      node->next = tmp->next;
      tmp->next = node;
      tmp = node->next;
    }

    tmp = head;
    while (tmp) {
      if (tmp->random) tmp->next->random = tmp->random->next;
      tmp = tmp->next->next;
    }

    tmp = head;
    while (tmp) {
      prev->next = tmp->next;
      prev = prev->next;
      tmp->next = tmp->next->next;
      tmp = tmp->next;
    }

    return dummy->next;
  }
};

时间复杂度 O ( n ) O(n) O(n)， n n n为原链表长度，空间 O ( 1 ) O(1) O(1)。