linked_list_copy

#include <stdio.h>
#include <stdlib.h>

#define LENGTH 10

typedef struct Node node;

struct Node
{
    int data;
    node *next;
    node *random;
};

void print(node *list)
{
    node *current = list;
    
    while (current) {
        printf("%d -- %d\n", current->data, current->random->data);
        current = current->next;
    }
}

node* create()
{
    size_t count = 0;
    size_t start = 0;
    size_t end = (LENGTH - 1);
    node *head = NULL;
    node *prev = NULL;
    node *current = NULL;
    node *last = NULL;
    
    // Create the standard linked list - increase length by 1 
    while (++count < (LENGTH + 1)) {
        current = malloc(sizeof(node));
        
        if (head == NULL)
            head = current;
        else
            prev->next = current;
        
        current->data = count;
        current->random = NULL;
        current->next = NULL;
        
        prev = current;
    }
    
    current = head;
    
    // Go through and assign the "random" pointer. Just make the first node's
    // random pointer look at the last node, and the last node's random pointer
    // look at the first node. Continue towards the middle of the list, and in
    // the event of an uneven list, have the middle node point to itself.
    while (start < (LENGTH / 2)) {
        // Get the last node for the current node
        last = current;
        for (count = start; count < end; count++) {
            last = last->next;
        }
        
        // Assign the random pointers
        current->random = last;
        last->random = current;
        
        // Change tracker counts and current node
        --end;
        ++start;
        current = current->next;
    }
    
    // Deal with an odd numbered list
    if (LENGTH / 2) {
        current->random = current;
    }
    
    return head;
}

void delete(node *list)
{
    node *current = list;
    node *prev = current;
    
    while (current) {
        prev = current;
        current = current->next;
        free(prev);
    }
}

void rollback(node *src, node *end)
{
    node *srcCurrent = src;
    node *temp = NULL;
    
    while (srcCurrent != end) {
        temp = srcCurrent->next;
        srcCurrent->next = srcCurrent->next->next;
        srcCurrent = srcCurrent->next;
        free(temp);
    }
}

node *copy(node *src)
{
    node *srcCurrent = src;
    node *cpyCurrent = NULL;
    node *newHead = NULL;
    
    // Insert a copy of the current node after itself
    while (srcCurrent) {
        // Make space for, and assign, copy data
        cpyCurrent = malloc(sizeof(node));
        if (cpyCurrent == NULL) {
            rollback(src, srcCurrent);
            return NULL;
        }
        cpyCurrent->data = srcCurrent->data;
        cpyCurrent->next = srcCurrent->next;
        
        // Insert the copied node (got next in previous line)
        srcCurrent->next = cpyCurrent;
        
        srcCurrent = srcCurrent->next->next;
    }
    
    srcCurrent = src;
    
    // Copy the random pointers
    while (srcCurrent) {
        srcCurrent->next->random = srcCurrent->random->next;
        srcCurrent = srcCurrent->next->next;
    }
    
    srcCurrent = src;
    cpyCurrent = srcCurrent->next;
    newHead = cpyCurrent;
    
    // Seperate the lists
    while (cpyCurrent->next) {
        // Original list
        srcCurrent->next = srcCurrent->next->next;
        srcCurrent = srcCurrent->next;

        // Copied list
        cpyCurrent->next = cpyCurrent->next->next;
        cpyCurrent = cpyCurrent->next;
    }
    srcCurrent->next = NULL;
    
    return newHead;
}

int main (void)
{
    node *head = NULL;
    node *cpy = NULL;

    // Make the list
    head = create();
    
    // Print the list
    print(head);
    
    cpy = copy(head);
    
    delete(head);
    
    print(cpy);
    
    return 0;
}