Create a copy of a linked list in which node contains a second pointer which may point to other nodes in linked list.
Easiest way to solve this problem is to allocate additional memory, where you will store map between pointer to node in a list you are trying to copy and pointer to node in new list.
Better solution for this problem relies on the fact that you can modify pointers in the original list you are copying. This makes algorithm more complicated, however allows to perform a copy in more optimal way(lower big-O complexity).
Idea behind the algorithm:
struct Node { int value; // value Node *next; // pointer to next element Node *second; // pointer to different element }; void copylistWithPointer(Node **dstRootPtr, const Node *srcRoot) { Node *currNode = srcRoot; if (dstRootPtr == NULL) return; if (srcRoot == NULL) return; // // First iteration - copy each element // while (currNode != NULL) { Node *newNode = new Node(); newNode->next = currNode->next; newNode->second = NULL; newNode->value = currNode->value; // change current node to point to new node currNode->next = newNode; // move to next node currNode = newNode->next; } // assign first newelement as root of new list *dstRootPtr = currNode->next; // // Second iteration - connect secondary pointers // currNode = srcRoot; while (currNode != NULL) { currNode->next->second = currNode->second->next; // move to next node currNode = currNode->next->next; } // // Third iteration - correct next pointers // currNode = srcRoot; while (currNode != NULL) { Node *secondListNode = currNode->next; // correct next pointer in first list currNode->next = secondListNode->next; // correct next pointer in second list if (secondListNode->next != NULL) { secondListNode->next = secondListNode->next->next; } // move to next node currNode = currNode->next; } }