一、题目描述
请实现函数 complex_list_node *clone_list(complex_list_node *head)，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的随机节点或 nullptr 。节点的 C++定义如下：
|
1 2 3 4 5 |
struct complex_list_node { int val; struct complex_list_node *next; struct complex_list_node *random; }; |
如下是一个复杂链表示例，其中虚线是 random 指针：
二、思路
复制过程可以分为三步，第一步，复制链表中的所有节点并插入到对应节点后，random 指针和原节点指针保持一致：
第二步，修改所有复制节点的 random 指针，修改成被复制出来的节点：
第三步，把所有新复制出来的节点从原始链表中移除：
三、代码实现
链表节点定义：
|
1 2 3 4 5 6 |
// 链表节点定义 struct complex_list_node { int val; struct complex_list_node *next; // 下一个节点 struct complex_list_node *random; // 随机节点 }; |
第一步克隆所有节点函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/* * 克隆所有的节点，并串到原始节点中去 * @head 链表的头结点 */ static void clone_all_nodes(complex_list_node *head) { complex_list_node *node, *clone; node = head; while (node) { // 拷贝节点 clone = new complex_list_node{node->val, node->next, node->random}; // 修改 p 节点的下一个节点指向新创建的节点 node->next = clone; // 移动 p 指针到下一个节点 node = clone->next; } } |
第二步修改 random 指针指向：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/* * 修正所有克隆节点的随机指针的地址 * @head 链表的头结点 */ static void fix_random_nodes(complex_list_node *head) { // node/q 节点分别表示原始节点和被克隆的节点 complex_list_node *node, *clone; node = head; while (node) { clone = node->next; // 修正 q 节点的 random 指针，注意 random 可能为 null if (clone->random) clone->random = clone->random->next; node = clone->next; } } |
第三步分离原始链表和新克隆链表：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/* * 修改新复制节点的指向，重新连接所有节点 * @head 头结点指针 * @return 新复制的链表头结点 */ static complex_list_node *reconnect_nodes(complex_list_node *head) { complex_list_node *node, *clone; complex_list_node *new_head = head->next; node = head; while (node) { clone = node->next; // 备份下一个节点的指针 node->next = clone->next; // 连接到新克隆的节点，注意 next 可能为 null if (clone->next) { clone->next = clone->next->next; } node = node->next; } return new_head; } |
整合起来的复杂链表拷贝函数：
|
1 2 3 4 5 6 7 |
complex_list_node *clone_complex_list(complex_list_node *head) { if (head == nullptr) return nullptr; clone_all_nodes(head); fix_random_nodes(head); return reconnect_nodes(head); } |
注意：这个函数里面一定要判断 head 是否为空的情况，前面三个函数因为是内部函数所以没有在入口判断 head 为空的情况！
四、单元测试
写代码容易，写单元测试麻烦，一个单元测试写了一小时。。。
4.1 链表创建函数
做单元测试，必不可少的一个测试函数是链表创建函数，因为要测试链表，首先要先创建链表：
|
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 |
/* * 链表创建函数 * @val 数据数组 * @random 随机指针 * @n 数组数量 * @return 返回链表头 */ static complex_list_node *list_creator(int data[], int random[], int n) { complex_list_node *head, **nodes, *p; int i; nodes = new p_complex_list_node[n]; // 创建所有的链表节点 for (i = 0; i < n; i++) { p = new complex_list_node{data[i], nullptr, nullptr}; nodes[i] = p; } // 连接所有的 next 和 random 指针 for (i = 0; i < n - 1; i++) { nodes[i]->next = nodes[i + 1]; if (random[i] == -1) { nodes[i]->random = nullptr; } else { nodes[i]->random = nodes[random[i]]; } } nodes[i]->random = nodes[random[i]]; p = nodes[0]; delete nodes; return p; } |
测试这个函数的正确性：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 测试创建链表的功能是不是 OK TEST(complex_list_node, list_creator) { // 数据数组 int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 随机指针数组 int random[10] = {2, 3, 6, -1, 3, 1, 0, 9, 5, 3}; int i; complex_list_node *head, *p, *r, *n; // 创建链表 head = list_creator(arr, random, 10); p = head; for (i = 0; i < 10 && p; i++, p = p->next) { r = p->random; EXPECT_EQ(p->val, arr[i]); if (random[i] == -1) { EXPECT_EQ(r, nullptr); } else { EXPECT_EQ(r->val, arr[random[i]]); } } } |
4.1 测试功能
测试功能点：
- 空链表测试
- 非空链表测试
- 链表克隆后是否会影响原始链表
leetcode 上也有这个一模一样的题目，下面的测试数据是基于 leetcode 来写的。
https://leetcode-cn.com/problems/copy-list-with-random-pointer/submissions/
TestFixtures 定义：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
const int leetcode_demo1_cnt = 5; class leetcode_test : public ::testing::Test { protected: void SetUp() override { // 初始化 list1 int arr[leetcode_demo1_cnt] = {7, 13, 11, 10, 1}; int random[leetcode_demo1_cnt] = {-1, 0, 4, 2, 0}; list1 = list_creator(arr, random, leetcode_demo1_cnt); // list2 为空 list2 = nullptr; } void TearDown() override { complex_list_node *p = list1, *next; while (p) { next = p->next; delete p; p = next; } } complex_list_node *list1; complex_list_node *list2; }; |
测试克隆链表案例：
|
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 |
TEST_F(leetcode_test, clone_nodes) { int i; complex_list_node *clone, *p, *q; clone = clone_complex_list(list1); p = list1; q = clone; // 遍历所有节点，所有节点的内容和原节点一样，并且克隆出来的节点并不是原链表上面的指针 for (i = 0; i < leetcode_demo1_cnt && p && q; i++, p = p->next, q = q->next) { // 两个节点不相等 EXPECT_NE(p, q); // 节点的值都一样 EXPECT_EQ(p->val, q->val); if (p->next) { EXPECT_TRUE(q->next); EXPECT_NE(p->next, q->next); } if (p->random) { EXPECT_TRUE(q->random); EXPECT_NE(q->random, p->random); } } // 都遍历的链表结尾了 EXPECT_FALSE(p); EXPECT_FALSE(q); EXPECT_EQ(i, leetcode_demo1_cnt); } |
测试空链表复制：
|
1 2 3 4 5 |
TEST_F(leetcode_test, empty_list) { complex_list_node *clone; clone = clone_complex_list(list2); EXPECT_FALSE(clone); } |
测试是否修改了原链表：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
TEST_F(leetcode_test, origin_list_not_modify) { int i = 0; complex_list_node *bak[leetcode_demo1_cnt], *p, *clone; // 备份原始链表的所有 next 指针 p = list1; while (p) { bak[i++] = p->next; p = p->next; } clone = clone_complex_list(list1); // 和克隆前的 next 指针对比，确认没有影响到原始指针 p = list1; i = 0; while (p) { EXPECT_EQ(bak[i++], p->next); p = p->next; } } |
测试结果：
