Copy Complex Node

Given a complex node, one pointer m_pNext points to the next node, and the other pointer m_pSibling points to the random node or NULL in the linked list. How to copy this complex linked list? Function: ComplexNode* Clone(ComplexNode* pHead).




The the first solution: use O(n) space to implement O(n) time performance.
The first step copys every node N of the linked list to a new node N', then connect all of these new nodes together. The trick is to build a haspmap stored into a pair . The second step is to find the corresponding node to copy the m_pSibling node of original linked list. Due to the hashmap, we can use O(1) to find S' from S.

The second solution is to implement O(n) performance without using additional space O(n).

In first step, we still copy a new node N' corresponding to the node N of original linked list. However, we put the N' back to the N as the following graph:





The second step is to copy the m_pSibling node of the original linked list. If the m_pSibling pointer of the node N of the original linked list points to S, then the m_pSibling pointer of the correspoinding node N' points to S' like the following graph.





The last step is to divide this linked list into two separate parts: the odd nodes belong to the original linked list; the even nodes belong to the new linked list.





The whole process is:


From Chinese version: http://zhedahht.blog.163.com/