Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the 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 representing Node.val
• random_index: the index of the node (range from 0 to n-1) where the random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Approach

Java

public class CopyListRandomPointer {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        Node temp = head.next;
        head.random = head;
        temp.random = head;
        head.random = head;
        head = copyRandomList(head);
        linkedListTraversal(head);
    }

    static Node copyRandomList(Node head) {
        Node curr = head, temp = null;
        if (head == null)
            return null;
        // insert duplicate node of every node into the list
        while (curr != null) {
            temp = curr.next;

            // create new node with the same value as of the
            // current node
            curr.next = new Node(curr.val);

            // settle the pointers
            curr.next.next = temp;

            // move to the next node
            curr = temp;
        }
        curr = head;
        while (curr != null) {

            // if current next is present then
            // mark the current random pointer
            if (curr.next != null)
                curr.next.random = curr.random != null ? 
                    curr.random.next : curr.random;

            // move to the next node
            curr = curr.next != null ? curr.next.next : curr.next;
        }
        Node original = head, copy = head.next;
        temp = copy;

        // settle the pointers in original and copy of
        // the list
        while (original != null && copy != null) {

            // if original next present then
            // move original to next of next of original
            original.next = original.next != null ? 
                        original.next.next : original.next;
            copy.next = copy.next != null ? copy.next.next : copy.next;

            // move to the next node in original of linked
            // list
            original = original.next;

            // move to the next node in the copy of linked
            // ist
            copy = copy.next;
        }
        return temp;
    }

    private static void linkedListTraversal(Node head) {
        Node temp = head;
        System.out.print("[");
        while (temp != null) {
            System.out.print("[");
            System.out.print(temp.val + ",");
            if (temp.random != null)
                System.out.print(temp.random.val);
            else
                System.out.print("null");
            System.out.print("]");

            temp = temp.next;
            if (temp != null)
                System.out.print(",");

        }
        System.out.print("]");
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int val;
    Node* next;
    Node* random;
    
    Node(int val) 
    {
        this->val = val;
        this->next = NULL;
        this->random = NULL;
    }
};

Node* copyRandomList(Node* head)
{
      Node *curr=head,*temp=NULL;
        if(head==NULL)
              return NULL;
    // insert duplicate node of every node into  the list
    while(curr)
      {
          temp=curr->next;

          //create new node with the same value as of the
          //current node
          curr->next=new Node(curr->val);

          //settle the pointers
          curr->next->next=temp;

          //move to the next node
          curr=temp;
      }
       curr=head;
      while(curr)
        {

            //if current next is present then
            //mark the current random pointer
            if(curr->next)
                  curr->next->random=curr->random?curr->random->next:curr->random;

            //move to the next node
            curr=curr->next?curr->next->next:curr->next;
        }
        Node *original=head,*copy=head->next;
        temp=copy;

       //settle the pointers in original and copy of
       //the list
        while(original&&copy)
        {

            //if original next present then
            //move original to next of next of original
            original->next=original->next?original->next->next:original->next;
            copy->next=copy->next?copy->next->next:copy->next;

            //move to the next node in original of linked
            //list
            original=original->next;

            //move to the next node in the copy of linked
            //ist
            copy=copy->next;
        }
        return temp;
}

//function to print the linked list
void printList(Node *head)
{
  Node *temp=head;
  cout<<"[";
  while(temp!=NULL)
    {
        cout<<"[";
        cout<<temp->val<<",";
        if(temp->random!=NULL)
          cout<<temp->random->val;
        else
         cout<<"null";
         cout<<"]";
        
        temp=temp->next;
        if(temp!=NULL)
          cout<<",";
        
    }
    cout<<"]";
}
int main()
{

  Node *head=new Node(1);
  head->next=new Node(2);
  Node *temp=head->next;
  head->random=head;
  temp->random=head;
  head->random=head;
  head=copyRandomList(head);
  printList(head);
  return 0;
}