Interview Classic 150 Problem 138: Copy List with Random Pointer

---

Timeline

Timeline

2025-11-20

init

linked list

---

Problem:

P138 Copy List with Random Pointer

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

At first I thought of using BFS, but it’s not that complicated; just use a hash table to store the mapping.

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

Alternatively, you can use a backtracking approach: recursively process each node of head. If the node has not been created yet, recursively create the node along with its next pointer and random pointer. If it has already been created, directly return the corresponding copied node.

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

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