Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Copy List with Random Pointer

Easy
0/40
Average time to solve is 10m
90 upvotes
Asked in companies
Cars24MyntraSprinklr

Problem statement

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

example

Random pointers are shown in red and next pointers in black.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10 ^ 2
0 <= N <= 10 ^ 3
0 <= DATA <= 10 ^ 6 and data != -1
-1 <= RANDOMINDEX < N

Where ‘T’ is the number of test cases, ‘N’ is the total number of nodes in the linked list, 'DATA' is the value of the linked list node and 'RANDOMINDEX' is the index of the node where the random pointer points to.

Time limit: 1 sec.
Sample Input 1:
1
1 2 2 0 3 4 4 4 5 1 -1
Sample Output 1:
true
Explanation of Sample Input 1:
For the first test case, “true” will be printed if the linked list is successfully cloned.

example

Sample Input 2:
2
1 1 2 1 -1
7 -1 13 0 11 4 10 2 1 0 -1
Sample Output 2:
true
true
Full screen
Console