一、题目描述
请实现函数complex_list_node *clone_list(complex_list_node *head)，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的随机节点或nullptr。节点的C++定义如下：
struct complex_list_node {
int val;
struct complex_list_node *next;
struct complex_list_node *random;
};
如下是一个复杂链表示例，其中虚线是random指针：
二、思路
复制过程可以分为三步，第一步，复制链表中的所有节点并插入到对应节点后，random指针和原节点指针保持一致：
第二步，修改所有复制节点的random指针，修改成被复制出来的节点：
第三步，把所有新复制出来的节点从原始链表中移除：
三、代码实现
链表节点定义：
// 链表节点定义
struct complex_list_node {
int val;
struct complex_list_node *next; // 下一个节点
struct complex_list_node *random; // 随机节点
};
第一步克隆所有节点函数：
/*
* 克隆所有的节点，并串到原始节点中去
* @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指针指向：
/*
* 修正所有克隆节点的随机指针的地址
* @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;
}
}
第三步分离原始链表和新克隆链表：
/*
* 修改新复制节点的指向，重新连接所有节点
* @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;
}
整合起来的复杂链表拷贝函数：
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 链表创建函数
做单元测试，必不可少的一个测试函数是链表创建函数，因为要测试链表，首先要先创建链表：
/*
* 链表创建函数
* @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;
}
测试这个函数的正确性：
// 测试创建链表的功能是不是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定义：
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;
};
测试克隆链表案例：
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);
}
测试空链表复制：
TEST_F(leetcode_test, empty_list) {
complex_list_node *clone;
clone = clone_complex_list(list2);
EXPECT_FALSE(clone);
}
测试是否修改了原链表：
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;
}
}
测试结果：
