## Interview Questions

### Clone a linked list with second pointer

Create a copy of a linked list in which node contains a second pointer which may point to other nodes in linked list.

View Solution

#### Algorithm concept

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:

- In first iteration - Insert new nodes between nodes in old list (next pointer from old node points to new now; new node next pointer points to old node next pointer)
- In second iteration - Go through nodes of old list (jumping every two nodes) and connect secondary pointers
- In third iteration - Correct next pointers in original lists

#### Complexity

Complexity of this algorithm is O(n).

In order to copy the list you need to traverse the list two times. This leads to complexity O(2n) which is same as O(n).

#### Solution

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;
}
}

#### References