Clone a linked list with random pointer

Clone a linked list having two pointers next and random


Category: Data Structure And Algorithms Tags: C#

Clone a linked list with random pointer - Code Files

Problem

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

LinkedList with extra random pointer
Fig 1: LinkedList with extra random pointer

 

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.

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

    var temp = original;
    while(temp != null)
    {
        // Adding copy to map
        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.

static void Print(Node head)
{
    var temp = head;
    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 };

    head.Next.Random = head.Next.Next.Next;
    head.Next.Next.Next.Random = head;

    Console.WriteLine("Original linked list");
    Print(head);
    var copy = CopyLinkedList(head);
    Console.WriteLine("Copied linked list");
    Print(copy);
}

Output

Original linked list

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

Copied linked list

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
Last modified on 11 March 2022
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 164
Questions: 16
Given Best Solutions: 16 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x