复杂链表的复制（C语言）

题目

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

算法原理

我们很容易能够根据next创建一个原链表的顺序链表，但是如何把random的指针指向正确的位置呢？我们很容易想到遍历的方法，如图所示：13的random指向7，那么我们只要遍历当结点的值满足7，再把13的random指向7就可以了，但是如果有两个结点的值是相同的这个方法就行不通了，而且这个方法的时间复杂度是O（n^2）。
这里我们介绍的方法是：建立原结点和拷贝结点之间的关系
1.拷贝结点值到原结点后面

2.控制拷贝结点的random：拷贝结点的random是原结点random->next
3.拷贝节点离开原结点，恢复原链表

代码实现

struct Node { 
    int val;          // 定义节点的值
    struct Node* next;  // 指向下一个节点的指针
    struct Node* random; // 指向随机节点的指针
};

struct Node* copyRandomList(struct Node* head) { 
    // 定义一个当前节点的指针 cur，初始化为头节点 head
    struct Node* cur = head; 
    while (cur) { 
        // 为新节点分配内存
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); 
        // 将当前节点的值复制到新节点中
        copy->val = cur->val; 
        // 获取当前节点的下一个节点
        struct Node* next = cur->next; 
        // 将当前节点的下一个指针指向新复制的节点
        cur->next = copy; 
        // 新复制节点的下一个指针指向原来的下一个节点
        copy->next = next; 
        // 移动到下一个节点
        cur = next;
        // 控制拷贝节点的 random
        cur = head; 
        while (cur) { 
            // 获取当前节点的下一个节点
            struct Node* copy = cur->next; 
            // 判断当前节点的 random 是否为空
            if (cur->random == NULL) {  // 这里将 = 改为 ==
                // 如果为空，将新节点的 random 设置为 NULL
                copy->random = NULL; 
            } 
            else { 
                // 否则，将新节点的 random 设置为当前节点的 random 的下一个节点
                copy->random = cur->random->next; 
            } 
            // 移动到下一个节点
            cur = copy->next; 
        } 
        // 用于保存拷贝后链表的头节点
        struct Node* copyHead = NULL; 
        // 用于保存拷贝后链表的尾节点
        struct Node* copyTail = NULL; 
        while (cur) { 
            // 获取当前节点的下一个节点
            struct Node* copy = cur->next; 
            // 获取下一个节点
            struct Node* next = copy->next; 
            // 如果尾节点为 NULL
            if (copyTail == NULL) { 
                // 将头节点设置为当前节点
                copyHead = copyTail = copy; 
            } 
            else { 
                // 将尾节点的下一个节点设置为当前节点
                copyTail->next = copy; 
                // 更新尾节点为当前节点
                copyTail = copyTail->next; 
                // 将当前节点的下一个节点设置为下一个节点
                cur->next = next; 
                // 移动到下一个节点
                cur = next; 
            } 
            // 返回拷贝后链表的头节点
            return copyHead; 
    } 
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67