gistfile1.cpp

//
//  main.c
//  CopyList
//
//  Created by Joshua Weinberg on 3/25/13.
//  Copyright (c) 2013 Joshua Weinberg. All rights reserved.
//

#include <iostream>
#include <map>

struct Node
{
    Node() : next(NULL) {};
    Node *next;
    Node *value;
};


//Assume singly linked
Node *copyNodes(Node *head)
{
    std::map<Node*,Node*> map;
    Node *n = head;
    Node *p = NULL;
    while (n)
    {
        map[n] = new Node();
        if (p)
            p->next = map[n];
        p = map[n];
        n = n->next;
    }
    
    n = head;
    while (n)
    {
        map[n]->value = map[n->value];
        n = n->next;
    }
    
    return map[head];
}

void printList(Node *head)
{
    Node *n = head;
    while (n)
    {
        std::cout << n << ": " << n->value << std::endl;
        n = n->next;
    }
}

int main(int argc, const char * argv[])
{
    Node n0, n1, n2, n3, n4, n5;
    n0.next = &n1;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = NULL;
    
    n0.value = &n2;
    n1.value = &n2;
    n2.value = &n1;
    n3.value = &n4;
    n4.value = &n1;
    n5.value = &n4;
    
    printList(&n0);
    
    Node *copy = copyNodes(&n0);
    
    printList(copy);
    
}