《剑指offer》面试题35：复杂链表的复制

2020年2月9日22:45:23数据结构和算法评论289字数 1100阅读3分40秒阅读模式

一、题目描述

请实现函数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;
};

struct complex_list_node {

int val;

struct complex_list_node *next;

struct complex_list_node *random;

};

如下是一个复杂链表示例，其中虚线是random指针：

《剑指offer》面试题35：复杂链表的复制-图片1

二、思路

复制过程可以分为三步，第一步，复制链表中的所有节点并插入到对应节点后，random指针和原节点指针保持一致：

《剑指offer》面试题35：复杂链表的复制-图片2

第二步，修改所有复制节点的random指针，修改成被复制出来的节点：

《剑指offer》面试题35：复杂链表的复制-图片3

第三步，把所有新复制出来的节点从原始链表中移除：

《剑指offer》面试题35：复杂链表的复制-图片4

三、代码实现

链表节点定义：

// 链表节点定义
struct complex_list_node {
    int val;
    struct complex_list_node *next; // 下一个节点
    struct complex_list_node *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;
    }
}

* 克隆所有的节点，并串到原始节点中去

* @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 链表的头结点

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;
}

* 修改新复制节点的指向，重新连接所有节点

* @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);
}

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;
}

* 链表创建函数

* @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]]);
        }
    }
}

// 测试创建链表的功能是不是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;
};

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, 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, 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;
    }
}