Katkat
Back

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

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement your own doubly linked list whose nodes also carry a special pointer to any node in the list, then write a deep clone without using a built-in list type or adding fields to the node class. It tests pointer handling, mapping nodes by identity, edge cases such as null or self pointers, and proving the copy is fully independent.

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.

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?

Hints

Hint 1

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 2

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.

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?