deep copy Linkedlist without destroying original list and extra storage space (using ANSI C)

Question

this linkedlist is different than normal linkedlists is that besides the next pointer, it also has a other pointer that points to another node except itself in the linkedlist.

so what's the best way to deep copy this linkedlist without destroying the original and no extra space?

My approach was simply doing a O(n^2) loop , but should be some smarter way.

Answer 1

You could branch your search at every node, and merge the paths back together when you encounter an already-visited node.

Answer 2

This implementation is completely untested, but the idea is very simple.

#include <stdlib.h>

struct node {
    struct node *next;
    struct node *what;
    void *data;
};

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 = malloc(sizeof(struct node));
        if (!new_node) abort();
        if (j) j->next = new_node;
        else new_root = new_node;
        new_node->data = i->data;
        i->data = new_node;
    }
    if (j) j->next = NULL;

    for (i = root, j = new_root; i; i = i->next, j = j->next)
        j->what = i->what->data;

    for (i = root, j = new_root; i; i = i->next, j = j->next)
        i->data = j->data;

    return new_root;
}

1. Following ->next on the original list, create a new list that mirrors it. Mangle ->data on each node in the old list to point to its corresponding node in the new list.
2. Walk through both lists in parallel and use the earlier mangled ->data to figure out where the ->what has gone to in the new list.
3. Walk through both lists in parallel and restore ->data to its original condition.

Note that this is 3 linear passes, thus its time is O(n), and it does not use any memory beyond what is needed to create the new list.