Deep Copy Linked List - O(n)

I'm trying to deep copy a linked list . I need an algorithm that executes in Linear Time O(n). This is what i have for now , but i'm not able to figure out what's going wrong with it. My application crashes and i'm suspecting a memory leak that i've not been able to figure out yet. This is what i have right now

 struct node {
    struct node *next;
    struct node *ref;
 };


struct node *copy(struct node *root) {
    struct node *i, *j, *new_root = NULL;

    for (i = root, j = NULL; i; j = i, i = i->next) {
        struct node *new_node;
        if (!new_node) 
        {
            abort();
        }
        if (j) 
        {
            开发者_运维技巧j->next = new_node;
        }
        else 
        {
            new_root = new_node;
        }

        new_node->ref = i->ref;
        i->ref = new_node;
    }
    if (j) 
    {
            j->next = NULL;
    }
    for (i = root, j = new_root; i; i = i->next, j = j->next)
        j->ref =i->next->ref;

      return new_root;
}

Can anyone point out where i'm going wrong with this ??

---

This piece alone:

    struct node *new_node;
    if (!new_node) 
    {
        abort();
    }

Seems good for a random abort() happening. new_node is not assigned and will contain a random value. The !new_node expression could already be fatal (on some systems).

As a general hint, you should only require 1 for-loop. Some code upfront to establish the new_root.

But atruly deep copy would also require cloning whatever ref is pointing to. It seems to me the second loop assigns something from the original into the copy. But I'm not sure, what is ref ?

---

One thing I immediately noticed was that you never allocate space for new_node. Since auto variables are not guaranteed to be initialized, new_node will be set to whatever value was in that memory before. You should probably start with something like:

struct node *new_node = (new_node *) malloc(sizeof(struct node));

in C, or if you're using C++:

node* new_node = new node;

Copying the list is simple enough to do. However, the requirement that the ref pointers point to the same nodes in the new list relative to the source list is going to be difficult to do in any sort of efficient manner. First, you need some way to identify which node relative to the source list they point to. You could put some kind of identifier in each node, say an int which is set to 0 in the first node, 1 in the second, etc. Then after you've copied the list you could make another pass over the list to set up the ref pointers. The problem with this approach (other that adding another variable to each node) is that it will make the time complexity of the algorithm jump from O(n) to O(n^2).

---

This is possible, but it takes some work. I'll assume C++, and omit the struct keyword in struct node.

You will need to do some bookkeeping to keep track of the "ref" pointers. Here, I'm converting them to numerical indices into the original list and then back to pointers into the new list.

node *copy_list(node const *head)
{
    // maps "ref" pointers in old list to indices
    std::map<node const *, size_t> ptr_index;
    // maps indices into new list to pointers
    std::map<size_t, node *>       index_ptr;

    size_t length = 0;
    node       *curn; // ptr into new list
    node const *curo; // ptr into old list

    node       *copy = NULL;

    for (curo = head; curo != NULL; curo = curo->next) {
        ptr_index[curo] = length;
        length++;

        // construct copy, disregarding ref for now
        curn = new node;
        curn->next = copy;
        copy = curn;
    }

    curn = copy;
    for (size_t i=0; i < length; i++, curn = curn->next)
        index_ptr[i] = curn;

    // set ref pointers in copy
    for (curo = head, curn = copy; curo != NULL; ) {
        curn->ref = index_ptr[ptr_index[curo->ref]];

        curo = curo->next;
        curn = curn->next;
    }

    return copy;
}

This algorithm runs in O(n lg n) because it stores all n list elements in an std::map, which has O(lg n) insert and retrieval complexity. It can be made linear by using a hash table instead.

NOTE: not tested, may contain bugs.