Interview Classic 150 Questions P138 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 wanted to use 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;
	}
};

You can also use a backtracking method, recursively traversing each node of head. If the node has not been created, then recursively create the node and its next pointer and random pointer. If it has been created, then directly return the original linked list node corresponding to that 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];
        }
};