Algorithm · Microsoft · Medium
Problem You are given a doubly linked list whose nodes each hold four fields: value, left, right, and special. left refers to the preceding node and right refers to the following node. special can refer to any node of the list, and it is allowed to refer to the node it belongs to. Produce a deep copy of the list. Every node in the copy must be newly allocated, with the same values and the same pointer structure as the original, and each non-null pointer inside the copy must…