Algorithm
Problem Name: 138. Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000-104 <= Node.val <= 104Node.randomisnullor is pointing to some node in the linked list.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct RandomListNode *copyRandomList(struct RandomListNode *head) {
struct RandomListNode **srcstack;
struct RandomListNode **dststack;
int *flagstack, found_cycle = 0;
int i, sp = 1, sz = 100;
struct RandomListNode *ret = NULL, *newnode, *newrandom, **prevp = NULL;
struct RandomListNode *node = head, *random;
srcstack = malloc(sz * sizeof(struct RandomListNode *));
dststack = malloc(sz * sizeof(struct RandomListNode *));
flagstack = malloc(sz * sizeof(int));
//assert(srcstack && dststack && flagstack);
srcstack[0] = dststack[0] = NULL;
while (node) {
i = 1;
while (i < sp && srcstack[i] != node) {
i ++;
}
if (i == sp) {
newnode = malloc(sizeof(struct RandomListNode));
//assert(newnode);
newnode->label = node->label;
newnode->next = NULL;
newnode->random = NULL;
if (sp == sz) {
sz = sz * 2;
srcstack = realloc(srcstack, sz * sizeof(struct RandomListNode *));
dststack = realloc(dststack, sz * sizeof(struct RandomListNode *));
flagstack = realloc(flagstack, sz * sizeof(int));
//assert(srcstack && dststack && flagstack);
}
srcstack[sp] = node;
dststack[sp] = newnode;
flagstack[sp] = 1;
sp ++;
} else {
newnode = dststack[i];
found_cycle = flagstack[i];
flagstack[i] = 1;
}
if (!ret) ret = newnode;
if (prevp) *prevp = newnode;
prevp = &newnode->next;
//if (found_cycle) break;
random = node->random;
i = 0;
while (i < sp && srcstack[i] != random) {
i ++;
}
if (i == sp) {
newrandom = malloc(sizeof(struct RandomListNode));
//assert(newrandom);
newrandom->label = random->label;
newrandom->next = NULL;
newrandom->random = NULL;
if (sp == sz) {
sz = sz * 2;
srcstack = realloc(srcstack, sz * sizeof(struct RandomListNode *));
dststack = realloc(dststack, sz * sizeof(struct RandomListNode *));
flagstack = realloc(flagstack, sz * sizeof(int));
//assert(srcstack && dststack && flagstack);
}
srcstack[sp] = random;
dststack[sp] = newrandom;
flagstack[sp] = 0;
sp ++;
} else {
newrandom = dststack[i];
}
newnode->random = newrandom;
node = node->next;
}
free(srcstack);
free(dststack);
return ret;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
unordered_mapm;
auto p = head;
while(p){
m[p] = new RandomListNode(p->label);
p = p->next;
}
p = head;
while(p){
m[p]->next = m[p->next];
m[p]->random = m[p->random];
p = p->next;
}
return m[head];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
Node curr = head;
while (curr != null) {
Node newNode = new Node(curr.val);
newNode.next = curr.next;
curr.next = newNode;
curr = newNode.next;
}
curr = head;
while (curr != null) {
curr.next.random = curr.random != null ? curr.random.next : null;
curr = curr.next.next;
}
Node oldCurr = head;
Node newCurr = head.next;
Node newHead = head.next; // Retain a pointer to copied list's head
// Separate merged lists into original list & copied list.
while (oldCurr != null) {
oldCurr.next = oldCurr.next.next;
newCurr.next = newCurr.next != null ? newCurr.next.next : null;
oldCurr = oldCurr.next;
newCurr = newCurr.next;
}
return newHead;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const copyRandomList = function(head) {
if (head == null) {
return null;
}
// Creating a new weaved list of original and copied nodes.
let ptr = head;
while (ptr != null) {
// Cloned node
const newNode = new RandomListNode(ptr.label);
A->A'->B->B'->C->C'
newNode.next = ptr.next;
ptr.next = newNode;
ptr = newNode.next;
}
ptr = head;
while (ptr != null) {
ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
ptr = ptr.next.next;
}
A'->B'->C'
let ptr_old_list = head; // A->B->C
let ptr_new_list = head.next; // A'->B'->C'
let head_old = head.next;
while (ptr_old_list != null) {
ptr_old_list.next = ptr_old_list.next.next;
ptr_new_list.next = (ptr_new_list.next != null) ? ptr_new_list.next.next : null;
ptr_old_list = ptr_old_list.next;
ptr_new_list = ptr_new_list.next;
}
return head_old;
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def copyRandomList(self, head: "Node") -> "Node":
dic = collections.defaultdict(lambda: Node(0, None, None))
dic[None] = None
n = head
while n:
dic[n].val = n.val
dic[n].next = dic[n.next]
dic[n].random = dic[n.random]
n = n.next
return dic[head]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0138_CopyListWithRandomPointer
{
public Node CopyRandomList(Node head)
{
if (head == null) return null;
var map = new Dictionary < Node, Node>();
var curr = head;
while (curr != null)
{
var clone = CloneNode(curr, map);
clone.next = CloneNode(curr.next, map);
clone.random = CloneNode(curr.random, map);
curr = curr.next;
}
return map[head];
}
private Node CloneNode(Node node, IDictionary < Node, Node> map)
{
if (node == null) return null;
if (map.ContainsKey(node)) return map[node];
var clone = new Node(node.val);
map[node] = clone;
return clone;
}
public class Node
{
public int val;
public Node next;
public Node random;
public Node() { }
public Node(int _val)
{
val = _val;
}
public Node(int _val, Node _next, Node _random)
{
val = _val;
next = _next;
random = _random;
}
}
}
}
Input
Output