Clone Linked List with Random Pointer Problem Statement
Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or null, your task is to create a deep copy of this linked list and return its head. The validation will be done to ensure the cloned linked list is an exact copy of the original.
Explanation:
A deep copy means creating new nodes rather than copying references of the original linked list's nodes.
Example:
Consider the following illustration where random pointers are shown in red and next pointers in black:
Input:
The first line contains an integer ‘T’, the number of test cases.
Each test case consists of a single line with nodes (value and random pointer index) separated by spaces. -1 is used for null values.
Each node is represented as a pair:
- Value: an integer for node value
- Random index: index for the node the random pointer points to or -1 if it's null
Output:
For each test case, output "true" if the linked list is successfully cloned.
Each output is on a new line for separate test cases.
Constraints:
1 <= T <= 10^2
0 <= N <= 10^3
(where N is the number of nodes)0 <= DATA <= 10^6
andDATA != -1
-1 <= RANDOMINDEX < N
Each node is represented by [value, randomIndex]
format, end of the list denoted by [-1]
.
Note:
You are required to implement the function; printing is handled separately.
Follow-up:
Can the cloning be accomplished without utilizing extra space?
Yes, the cloning of a linked list with random pointer can be accomplished without utilizing extra space.
Use a hashmap to store the mapping between original nodes and their corresponding cloned nodes.
I...read more
Top Times Internet Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Times Internet Software Developer
Reviews
Interviews
Salaries
Users/Month