Linked list problems

Question

Possible Duplicate:
Copy a linked list

Hello stackoverflow! I am trying to learn more about linked lists so I am trying to create a function that deep copies a linked list. I've got this under control. The hard part is that the input list is going to contain nodes that reference other random nodes within the list.

First problem is that I don't know how to create the 'random' nodes within the list. As of now, I just have the 'random' nodes equal to the 'next' nodes.

For example... pNext references the next value, but pReference will reference a random node in the list. Like pReference 1 references 3, 2 references 4, 3 references 1, and 4 references 1.

Second problem is that my code is coping the 'random' node values but it is dependent on the original copy. I want it to be a deep copy and not dependent on the original.

#include <iostream>
#include <stdio.h>

using namespace std;

struct Node
{
    int Number; // An integer value.
    Node *pNext; // A pointer to the next node within the list.
    Node *pReference; // A pointer to a random node within the list.
};

void push(Node** head, int data, Node* reference)
{
    Node* newNode = new Node; 
    newNode->Number = data;
    newNode->pNext = *head;
    newNode->pReference = reference;
    *head = newNode;
}

Node* DuplicateLinkedList(Node *head)
{
    Node* current = head;
    Node* newHead = NULL;
    Node* newTail = NULL;

    while(current != NULL)
    {
        if(newHead == NULL)
        {
            push(&newHead, current->Number, (current->pReference));
            newTail = newHead;
        }
        else
        {
            push(&(newTail->pNext),current->Number, (current->pReference));
            newTail = newTail->pNext;
        }
        current = current->pNext;
    }

    return newHead;
}

int main()
{
    Node* headOfList= NULL;

    //Creating List for verification.
    for(int i=6; i>=1;i--)
    {
        push(&headOfList, i, headOfList);
    }

    //Call duplicate function.
    Node* copiedList = DuplicateLinkedList(headOfList);

    //Output for verification
    cout << endl << "Original: " << endl;
    while(headOfList != NULL)
    {
        cout << "Number: " << headOfList->Number << " ";
        cout << "pNext: " << headOfList->pNext << " ";
        cout << "pReference: " << headOfList->pReference << " " << endl;
        headOfList = headOfList->pNext;
    }
    cout << endl << endl;

    cout << endl << "Copied: " << endl;
    while(copiedList != NULL)
    {
        cout << "Number: " << copiedList->Number << " ";
        cout << "pNext: "  << copiedList->pNext << " ";
        cout << "pReference: " << copiedList->pReference << " " << endl;
        copiedList = copiedList->pNext;
    }
    cout << endl << endl;


    system("pause");
}

Answer 1

Use a std::map to store the conversion between the original and the new pointers.

Walk the list two times: one time to create the new nodes (with pReference set to NULL) and to populate the map, a second time to fill in the pReference member by looking them up in the map.

Untested code:

Node* CopyNode(Node* src)
{
  if (src == NULL) return NULL;

  Node* newNode = new Node;
  newNode->number = src->number;
  newNode->pNext = NULL;
  newNode->pReference = NULL;

  return newNode;
}

Node* DeepCopy(Node* head)
{
  if (head == NULL) return NULL;

  std::map<Node*, Node*> mappings;

  Node* newHead = copyNode(head);
  mappings[head] = newHead;

  Node* newCurrent = newHead;
  for (Node* next = head->pNext; next != NULL; next = next->pNext)
  {
    Node* copy = CopyNode(next);
    mappings[next] = copy;

    newCurrent->pNext = copy;
    newCurrent = copy;
  }

  for (Node* current = head; current != NULL; current = current->pNext)
  {
    Node* newCurrent = mappings[current];
    newCurrent->pReference = mappings[current->pReference];
  }

  return newHead;
}

Answer 2

Here is a very slick algorithm I learned to get a random element from a list in O(N) time when you don't have the size of the list.

Node* GetRandomNode(Node* head)
{
 int i = 1;
 srand ( time (NULL) );
 Node* temp = head;
 while ( head != NULL )
 { 
   if ( rand() % i == 0 ) temp = head;
   head = head->pNext;
   i++; 
 }

 return temp;
}

So you can just call this function with the head of your list for each node to get a uniformly distributed random node.

As for your deep copy problem, you just have to allocate a new node and copy the value of your node into it.

Answer 3

How about simplifying.
I usually write the recursive solution first then translate that into a loop:

Node* DuplicateLinkedList(Node* list)
{
    std::map<Node*,Node*>   nodeMap;
    Node* result = DuplicateNode(nodeMap, list);
    resetRandomNodes(nodeMap, result);
    return result;
}

Node* DuplicateNode(std::map<Node*,Node*>& nodeMap, Node *node)
{
    if (node== NULL)
    {    return NULL;
    }

    Node* result = new Node(node->Number, 
                            // Recursively copy the next element
                            DuplicateNode(nodeMap, node->pNext),
                            // For now store the original rand element
                            // We will fix this by iterating over the list again 
                            node->pReference
                           );
    // Keep a record of which node maps to which new node.
    nodeMap[node] = result;

    return result;
}

void resetRandomNodes(std::map<Node*,Node*>& nodeMap, Node *node)
{
    if (node== NULL)
    {    return;
    }

    // Remember we stored the original random node (from the src list) in pReference.
    // Now we must replace this with the correct value. We can look this up in the
    // nodeMap we created when we copied the loop.
    node->pReference = nodeMap[node->pReference];

    // Recursively go through list.
    resetRandomNodes(nodeMap, node->pNext);
}

Now to make it efficient you just need to translate the recursion into a loop. Should be relatively trivial. Once you have done that you can merge the three functions into one.