力扣-138-复杂链表的复制/剑指Offer-35-复杂链表的复制

与复制普通链表的区别在于：多出了一个随机指针

我们考虑下复制一个普通链表：

1. 遍历并复制节点i，让构造的他的上一个节点指向i
   看起来只需要2个指针，指针1指向当前构造的节点，指针2指向构造的上一个节点
   这两个指针应该是指向的原链表

但是所谓的复杂链表复制，麻烦的点就在于：随机指针指向的是不确定的位置
如果构建过程中指向，那么被指向节点可能都还没创建
那么我们想考虑复制一条单链表，然后再去遍历一次处理随即指针？但是这样做仍然有问题，单链表怎么找到随机一个节点呢？用HashMap？空间复杂度太大了吧
理论上是可行的，但是不优雅

朴素的直接思路

《剑指Offer》给出的常规方法和我想的一样

1. 先把指向后一个节点的单链表复制出来，一次遍历，同时将节点指针保存在一个hashmap中
2. 再遍历一次，为每个节点设置随机指针，去 hashmap 里面找指定节点的位置

这相当于一种以空间换时间的做法——利用额外 hashmap O(n)的空间去节省每一次都需要遍历链表去查找指定节点的时间

尽管如此 2N 的时间复杂度 和 N 的空间复杂度仍然算不上优秀

回溯

最优解

接下来我们考虑另一种方法

第一趟同样是复制单链表，但是不同的是这次我们将复制出来的每个新节点放在原节点的后面

为什么？因为这样就在不许要额外空间的情况下记录了每个原节点的位置

		Node* traverse = head;// 不修改原指针
		while (traverse) {
			Node* node = new Node(traverse->val);
			node->next = traverse->next;
			traverse->next = node;
			traverse = traverse->next;
		}

然后是第二趟，处理每个节点的随机指针
这里就能体现出 将新节点放在原节点后面的好处了，这里就像是一个map一样，我们可以很方便地知道复制节点随机指针所指向节点地位置——就在原随机节点的后面，原随机节点我们是知道的

		while (traverse) {
			// 复制节点的随机指针指向的是原节点的随即指针指向节点的后一个位置
			traverse->next->random = head->random->next;
			traverse = traverse->next->next;// 向后移动两个位置
		}

最后一步是将原链表和复制后的新链表分开
...
第一版AC代码

	Node* copyRandomList(Node* head) {
		if (!head) return nullptr;

		Node* traverse = head;// 不修改原指针
		while (traverse) {
			Node* node = new Node(traverse->val);
			node->next = traverse->next;
			traverse->next = node;
			traverse = node->next;
		}
		traverse = head;// 指向新链表头
		while (traverse) {
			// 要特别注意随机指针为空的情况
			if (traverse->random) {
				// 复制节点的随机指针指向的是原节点的随即指针指向节点的后一个位置
				traverse->next->random = traverse->random->next;
			}
			else traverse->next->random = nullptr;
			traverse = traverse->next->next;// 向后移动两个位置
		}

		traverse = head;
		Node* nxt = head->next->next;
		Node* new_head = head->next;// 保存新链表的头节点，作为返回值
		// 当新复制节点存在时
		while (nxt) {
			traverse->next->next = traverse->next->next->next;// 复制节点random
			traverse->next = nxt;

			traverse = traverse->next;
			nxt = traverse->next->next;
		}
        traverse->next = nullptr;

		return new_head;
	}

注意跟上面的分步代码不一样，上面的代码是有问题的，需要注意的是：

1. 原节点的 random 指针可能为空指针，所以在处理复制节点的 random 指针的时候直接random->next就会出现空指针异常
2. 按照我的拆分方法，最后一步必须补上一句traverse->next = nullptr;，不然会导致原链表的最后一个节点未分开，我会尝试一下有没有更优的写法

仍旧，链表题的考察重点还是考察对指针的操作

保留一下测试代码：

void printList(Node* head) {
	Node* traverse = head;
	while (traverse)
	{
		cout << traverse->val << " ";
		traverse = traverse->next;
	}
	cout << endl;
}

		//printList(new_head);
		//printList(head);