Copy Linked List with Arbitrary Pointer

Make a deep copy of the given linked list where each node has two pointers, a regular next pointer and an arbitrary pointer.

Statement

We are given a linked list where the node has two pointers:

  1. The first is the regular next pointer.
  2. The second pointer is called an arbitrary pointer, and it can point to any node in the linked list.

Also, each node has member data which holds the data of the node. Our task is to write code to make a deep copy of the given linked list.

Note: Here, deep copy means that any operations on the original list (inserting, modifying, and removing) should not affect the copied list and any operations on the copied list should not affect the original list.

Example

An example of a linked list with arbitrary pointers connected is given below.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.