【复杂链表的复制】

前言

打怪升级：第3天

---

一、复杂链表的复制

剑指 Offer 35. 复杂链表的复制

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

首先分析题目：需要我们进行链表的拷贝，如果只是单链表拷贝的问题的话这个问题就很简单了，不过该链表有所不同：添加了一个random指针，我们在复制链表时也要保证复制的链表的random指针指向的节点位置和原链表random指针指向的节点位置相同，那么这里就是本题的复杂处所在了。
难点：确定random指针的指向
解决方法：我们在创建好新链表之后再设置random指针，每次设置random指针时都遍历一次原链表，找到该节点的random指针指向的是链表的第几个节点，之后遍历拷贝链表进行连接即可，当然这种方法的时间复杂度就非常的不善喽–O(n^2)，不过这也是计算机最擅长的计算嘛。

那么下面，我们不考虑上面的方法，这次我们一起来了解一种特殊的一般“打破脑袋”也想不到的方法：将拷贝链表按照一定的规律连接到原链表上，在原链表上进行操作。
具体过程与实现且看下文。

（一）创建并链接拷贝节点

1.题目分析

我们在插入链表时将新的节点插入到被拷贝节点的后面

视频解析：

复杂链表复制--1

2.具体代码

示例：

	//1. 创建并链接拷贝节点
	Node* cur = head;
	while (cur)
	{
		Node* cpy = (Node*)malloc(sizeof(Node));
		//random指针置空或者不置空都可以
        cpy->val = cur->val;
	    cpy->next = cur->next;

		cur->next = cpy;
		cur = cpy->next;
	}
1
2
3
4
5
6
7
8
9
10
11
12

（二）设置random指针

1.题目分析

图画分析：

视频解析：

复杂链表复制--2

2.具体代码

示例：

//2. 链接random指针
	cur = head;
	while (cur)
	{
		Node* cpy = cur->next;

		if (cur->random == NULL)
			cpy->random = NULL;
		else
		{ // 新节点都链接在原节点的后面
			cpy->random = cur->random->next;
		}

		cur = cpy->next;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（三）分离拷贝链表并恢复原链表

1.题目分析

拷贝节点的random指针设置完毕我们就要将它从原链表中分离出来，而至于原链表需不需要复原这个需要看题目要求的，
不过，我们跟着“原链表大哥”闯天下，现在想要走出来“单干”也不能忘了“大哥”的往日情意啊，所以我们还是把原链表复原比较好。

视频解析：

复杂链表复制--3

2.具体代码

示例：

//3. 分离拷贝节点并恢复原链表
	cur = head;
	Node* phead = cur->next;
	while (cur)
	{
		Node* cpy = cur->next;

		cur->next = cpy->next;
		// 此处需要注意：防止对空指针的解引用
		if (cur->next == NULL)
			break;
		cpy->next = cur->next->next;

		cur = cur->next;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、整体代码

示例：

Node* copyRandomList(Node* head) {
	if (head == NULL)
		return head;

	//1. 创建并链接拷贝节点
	Node* cur = head;
	while (cur)
	{
		Node* cpy = (Node*)malloc(sizeof(Node));
		cpy->val = cur->val;
		cpy->next = cur->next;

		cur->next = cpy;
		cur = cpy->next;
	}

	//2. 设置random指针
	cur = head;
	while (cur)
	{
		Node* cpy = cur->next;

		if (cur->random == NULL)
			cpy->random = NULL;
		else
		{ // 新节点都链接在原节点的后面
			cpy->random = cur->random->next;
		}

		cur = cpy->next;
	}

	//3. 分离拷贝节点并恢复原链表
	cur = head;
	Node* phead = cur->next;
	while (cur)
	{
		Node* cpy = cur->next;

		cur->next = cpy->next;
		if (cur->next == NULL)
			break;
		cpy->next = cur->next->next;

		cur = cur->next;
	}

	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

提交实例：

---

总结

以上就是今天讲解的复杂链表复制的全部内容，这里的第二种方法的确非常难以想到，这些由大神们神奇的脑回路所创造创造之物我们需要做的就是理解它并记住它即可，既然成不了巨人那就站到巨人的肩膀上。
如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。