Coderust: Hacking the Coding Interview/

...

/

Copy Linked List with Arbitrary Pointer

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.

We'll cover the following...

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.

Sample input

 [7 (21), 14 (null), 21 (7)]

Expected output

 [7 (21), 14 (null), 21 (7)]

Note: Deep copied list remains unchanged if the original list is modified.

Try it yourself

main.cpp
ArbPointerLinkedList.cpp
LinkedList.cpp
LinkedListNode.cpp
#include <vector>
#include <unordered_map>
#include "ArbPointerLinkedList.cpp"
using namespace std;
typedef LinkedListNode* NodePtr;
NodePtr DeepCopyArbitraryPointer(NodePtr head) {
	//TODO: Write - Your - Code
	return nullptr;
}

Solution 1

This approach uses a map to track arbitrary nodes pointed by the original list. We will create a deep copy of the original linked list in two passes:

  1. In the first pass, create a copy of the original linked list. While creating this copy, use the same values for data and the arbitrary pointer in the new list. Also, ...