# Clone a linked list having two pointers next and random

 Category: Data Structure And Algorithms Tags:

## Problem

Given linked list below, we have to create a new copy of the linked list.

Random pointer can point to any node in linked list and Next pointer points to next element. If there is only next pointer it is easier to make copy of linked list but with random pointer we should have all the nodes already created before assigning random pointer.

## Solution

Creating Node structure for linked list.

public class Node
{
public int Data;
public Node Next;
public Node Random;
}

To solve this we will use O(n) extra space to store copy of nodes in a Dictionary which maintains mapping between original and copied nodes.

{
//Key is original node and Value is Copied node
Dictionary<Node, Node> originalToCopyMapping = new Dictionary<Node, Node>();

var temp = original;
while(temp != null)
{
originalToCopyMapping[temp] = new Node() { Data = temp.Data };
temp = temp.Next;
}

foreach (Node originalNode in originalToCopyMapping.Keys)
{
var copiedNode = originalToCopyMapping[originalNode];

// Setting Next and Random pointers
if (originalNode.Next != null)
copiedNode.Next = originalToCopyMapping[originalNode.Next];
if (originalNode.Random != null)
copiedNode.Random = originalToCopyMapping[originalNode.Random];
}

return originalToCopyMapping[original];
}

Above method returns head of new copy. Lets create another method to print the linked list.

{
while (temp != null)
{
var randomPointsTo = temp.Random != null ? temp.Random.Data : -1;
Console.WriteLine(\$"Node {temp.Data}, Node's Random points to { randomPointsTo }");
temp = temp.Next;
}
}

Print method print all the elements from head to tail also which node random pointer points to. -1 means random pointer points nowhere.

static void Main(string[] args)
{
var head = new Node() { Data = 1 };
head.Next = new Node() { Data = 2 };
head.Next.Next = new Node() { Data = 3 };
head.Next.Next.Next = new Node() { Data = 4 };

Print(copy);
}

Output

Node 1, Node's Random points to -1

Node 2, Node's Random points to 4

Node 3, Node's Random points to -1

Node 4, Node's Random points to 1

Node 1, Node's Random points to -1

Node 2, Node's Random points to 4

Node 3, Node's Random points to -1

Node 4, Node's Random points to 1

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 158 Questions: 16 Given Best Solutions: 16 *