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:

example

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 and DATA != -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?
AnswerBot
2d

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 cloned nodes.

  • Iterate through the o...read more

Help your peers!
Add answer anonymously...
Urban Company Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter