Deep-Clone a Hand-Built Doubly Linked List with an Arbitrary Special Pointer

Implement a doubly linked list in which every node has four fields: - `value`: the node's value (assume an integer); - `left`: the previous node, or null for the first node; - `right`: the next node, or null for the last node; - `special`: a pointer that may point to any node in the same list. Then write a method that returns a complete, independent copy (a deep clone) of a list. Do not use your language's built-in linked list (for example, Java's `LinkedList`). Define both the node class and the linked list class yourself, with whatever operations you need to build a list. ```hint Copy the shape first Getting the values and the `left`/`right` links into a new list is the easy half. Decide what you need to remember during that pass so that the `special` links can be filled in afterwards. ``` ```hint Check where every link points Assigning a pointer field copies a reference, not a node. After cloning, ask of every `left`, `right` and `special` link in the copy which of the two lists it points into. ``` ### Constraints and Clarifications - In the copy, every `left`, `right` and `special` pointer must point to a node of the copy, never to a node of the original list. - The copy has the same values in the same order. If an original node's `special` points to the node at some position of the original list, the corresponding copied node's `special` points to the node at that same position of the copy. - Do not add fields to the node class, such as a position index, to make cloning easier. Keep any bookkeeping inside the cloning code, and leave the original list as it was. - Assume values may repeat, so a node cannot be identified by its value. ### Clarifying Questions - Can a node's `special` pointer be null, or point to the node itself? - Does the list class keep only a head pointer, or a head, a tail and a size? - May the original list be modified temporarily during cloning if it is fully restored before the method returns? ### What a Strong Answer Covers - Small, correct node and list classes, with an append operation that maintains links in both directions - A way to find each original node's copy that depends on node identity, not on values - All three kinds of links pointing into the copy, including the ends of the list and null or self-referencing `special` pointers - The original list and the node class left unchanged - Time and space complexity, and a convincing way to test that the copy is deep ### Follow-up Questions - Can you clone the list with only constant extra memory besides the new nodes? What does that require you to do to the original list, and does it fit the constraint above? - How would you write a test that fails for a shallow copy but passes for a deep one? - How would your approach change if `special` pointers could also point into other lists? - How would you clone a general graph of nodes, where links can form cycles, instead of a list?