leetcode138.随机链表的复制

题目链接

leetcode

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
代码只接受原链表的头节点 head 作为传入参数。

C++ 代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 链表结点的定义
struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

// 辅助函数：创建链表
Node* createList(const vector<int>& nums) {
    Node* dummy = new Node(-1);
    Node* cur = dummy;
    for (int num : nums) {
        cur->next = new Node(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(Node* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->random != nullptr) {
            cout << "(random: " << head->random->val << ") ";
        } else {
            cout << "(random: null) ";
        }
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(Node* head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    回溯 + 哈希表

    哈希表优化：
        使用一个哈希表来存储原始结点和其复制结点之间的映射关系。
        在复制过程中，如果已经复制过某个结点，则直接从哈希表中获取其复制结点。
    复制链表：
        对于链表中的每个结点，先检查哈希表中是否已经存在该结点的复制结点。
        如果不存在，则创建新的复制结点，并将其添加到哈希表中。
        然后，复制该结点的 next 和 random 指针。
    递归复制：
        对于 next 和 random 指针指向的结点，递归调用 copyRandomList 函数进行复制。

    时间复杂度：O(n)
        其中 n 是链表的长度。对于每个结点，
        至多访问其「后继结点」和「随机指针指向的结点」各一次，均摊每个点至多被访问两次。
    空间复杂度：O(n)
        哈希表的空间开销。
        返回值不计入空间复杂度。
*/
class Solution_0 {
public:
    unordered_map<Node*, Node*> cachedNode;

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

        if (!cachedNode.count(head)) {
            Node* newHead = new Node(head->val);
            cachedNode[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }

        return cachedNode[head];
    }
};

/*    
    迭代 + 结点拆分
    每个结点后面复制一个结点，然后再分离出来。
    
    时间复杂度：O(n)
        其中 n 是链表的长度，需要遍历该链表三次。
    空间复杂度：O(1)
        返回值不计入空间复杂度。
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;

        // 复制原链表中的各个结点，构建新的链表
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* newNode = new Node(node->val);
            newNode->next = node->next;
            node->next = newNode;
        }

        // 修改新链表中各个结点的 random 指向
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* newNode = node->next;
            newNode->random = (node->random != nullptr) ? node->random->next : nullptr;
        }

        // 拆分出原链表、新链表
        Node* newHead = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* newNode = node->next;
            node->next = node->next->next;
            newNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr;
        }

        return newHead;
    }
};

// 思路同上
class Solution_2 {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;

        // 复制原链表中的各个结点，构建新的链表
        copyList(head);
        // 修改新链表中各个结点的 random 指向
        connectRandomNodeList(head);
        // 拆分出原链表、新链表
        return recopyList(head);
    }

    void copyList(Node* head) {
        Node* node = head;
        while (node != nullptr) {
            Node* temp = new Node(node->val);
            temp->next = node->next;
            node->next = temp;
            node = temp->next;
        }
    }
    
    void connectRandomNodeList(Node* head) {
        Node* node = head;
        Node* copyNode = head->next;
        while (node != nullptr) {
            if (node->random != nullptr)
                copyNode->random = node->random->next;
            node = copyNode->next;
            if (node != nullptr)
                copyNode = node->next;
        }
    }

    Node* recopyList(Node* head) {
        Node* node = head;
        Node* copyNode = head->next;
        Node* copyNodeHead = head->next;
        while (node != nullptr) {
            node->next = copyNode->next;
            node = node->next;
            if (node != nullptr)
                copyNode->next = node->next;
            copyNode = copyNode->next;
        }

        return copyNodeHead;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {0, 1, 2, 3, 4};
    Node* head = createList(nums);
    // 创建 random 指针
    head->random = head->next->next;
    head->next->random = head->next->next->next;
    head->next->next->random = head->next->next;
    head->next->next->next->random = head->next->next->next->next;
    head->next->next->next->next->random = head->next->next;

    // 复制链表
    Node* copy = solution.copyRandomList(head);

    // 打印结果
    cout << "Original List: " << endl;
    printList(head);
    cout << "Copy List: " << endl;
    printList(copy);

    // 释放内存
    deleteList(head);
    deleteList(copy);

    return 0;
}

Golang 代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package main

import "fmt"

// 定义链表节点
type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

// createLinkedList 创建随机链表
func createLinkedList(values [][2]int) *Node {
	if len(values) == 0 {
		return nil
	}
	nodes := make([]*Node, len(values))
	for i, val := range values {
		nodes[i] = &Node{Val: val[0]}
	}
	for i := 0; i < len(values)-1; i++ {
		nodes[i].Next = nodes[i+1]
	}
	for i, val := range values {
		if val[1] != -1 {
			nodes[i].Random = nodes[val[1]]
		}
	}
	return nodes[0]
}

// printLinkedList 打印链表
func printLinkedList(head *Node) string {
    var result []string
	nodes := []*Node{} // 用于存储链表的所有节点
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}

	for node := head; node != nil; node = node.Next {
		randomIndex := -1
		if node.Random != nil {
			for i, n := range nodes {
				if n == node.Random {
					randomIndex = i
					break
				}
			}
		}
		result = append(result, fmt.Sprintf("[%d %d]", node.Val, randomIndex))
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路： 
        1.在原链表的每个节点后插入对应的复制节点。
        2.根据原节点的随机指针设置复制节点的随机指针。
        3.将原链表和复制后的链表分离。
    
    时间复杂度：O(n)
        其中 n 是链表的长度，需要遍历该链表三次。
    空间复杂度：O(1)
        几个固定的指针变量，不需要额外的空间。
*/
func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // 复制节点，并将新节点插入到原节点之后
    for node := head; node != nil; node = node.Next.Next {
        newNode := &Node{Val: node.Val}
        newNode.Next = node.Next
        node.Next = newNode
    }

    // 设置新节点的随机指针
    for node := head; node != nil; node = node.Next.Next {
        if node.Random != nil {
            node.Next.Random = node.Random.Next
        }
    }

    // 分离原链表和新链表
    newHead := head.Next
    for node := head; node != nil; node = node.Next {
        newNode := node.Next
        node.Next = node.Next.Next
        if newNode.Next != nil {
            newNode.Next = newNode.Next.Next
        }
    }

    return newHead
}

func main() {
    // 测试用例
	testCases := []struct {
		values   [][2]int
		expected [][2]int
	}{
		{
			values:   [][2]int{{7,-1}, {13,0}, {11,4}, {10,2}, {1,0}},
			expected: [][2]int{{7,-1}, {13,0}, {11,4}, {10,2}, {1,0}},
		},
		{
			values:   [][2]int{{1,1}, {2,1}},
			expected: [][2]int{{1,1}, {2,1}},
		},
		{
			values:   [][2]int{{3,-1}, {3,0}, {3,-1}},
			expected: [][2]int{{3,-1}, {3,0}, {3,-1}},
		},
    }

    for i, tc := range testCases {
		head := createLinkedList(tc.values)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
		result := copyRandomList(head)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}
#leetcode
leetcode138.随机链表的复制
https://lcf163.github.io/2024/04/07/leetcode138：随机链表的复制/
作者
乘风的小站
发布于
2024年4月7日
许可协议