面试经典150题 P138 随机链表的复制

---

时间轴

2025-11-20

init

---

题目：

P138 随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150

最开始我本想用 BFS，但其实没这么麻烦，用哈希表存储映射关系即可。

#include <stddef.h>
#include <unordered_map>

using std::unordered_map;
class Node {
    public:
	int val;
	Node *next;
	Node *random;

	Node(int _val)
	{
		val = _val;
		next = NULL;
		random = NULL;
	}
};

class Solution {
    public:
	Node *copyRandomList(Node *head)
	{
		// DFS
		unordered_map<Node *, int> original_nodemap;
		unordered_map<int, Node *> new_nodemap;
		Node *p = head, *new_head = new Node(-1), *q = new_head;

		int i = 0;
		while (p != NULL) {
			q->next = new Node(p->val);
			q = q->next;
			new_nodemap[i] = q;
			original_nodemap[p] = i;
			i++;
			p = p->next;
		}

		q = new_head;
		new_head = new_head->next;
		delete q;

		q = new_head;
		p = head;
		while (q != NULL && p != NULL) {
			if (p->random == NULL) {
				q->random = NULL;
			} else {
				q->random = new_nodemap[original_nodemap[p->random]];
			}

			q = q->next;
			p = p->next;
		}

		return new_head;
	}
};

也可以使用回溯的方法，递归head的每个节点，如果该节点没有被创建过，那么就递归的创建该节点及其 next 指针域和 random 指针域。如果已经创建过，那么直接返回该节点对应的原链表节点。

class Solution {
public:
    unordered_map<Node*, Node*> cachedNode;

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

hot 100 rewrite

class Node {
    public:
        int val;
        Node *next;
        Node *random;

        Node(int _val)
        {
                val = _val;
                next = nullptr;
                random = nullptr;
        }
};

#include <unordered_map>
#include <vector>
using std::unordered_map;
using std::vector;

class Solution {
    public:
        Node *copyRandomList(Node *head)
        {
                if (head == nullptr)
                        return nullptr;

                unordered_map<Node *, int> node_index;

                Node *p = head;
                int i, n = 0;
                while (p != nullptr) {
                        node_index[p] = n++;
                        p = p->next;
                }

                vector<Node *> vec(n);
                p = head;
                for (i = 0; i < n; i++) {
                        vec[i] = new Node(p->val);
                        p = p->next;
                }

                p = head;
                for (i = 0; i < n; i++) {
                        vec[i]->next = (i == (n - 1) ? nullptr : vec[i + 1]);

                        vec[i]->random = (p->random == nullptr) ? nullptr :
                                                                  vec[node_index[p->random]];
                        p = p->next;
                }

                return vec[0];
        }
};