Thread: Copy List with random pointer

Write code to create a copy of a linked list with two pointers, one pointing to the next node and another one to any random node of the List.

Code:

struct linkedList {
	int data;
	struct linkedList* next;
	struct linkedList* random;
};

typedef struct linkedList* List;

// Not for this list structure
List randomCopy(List L)
{
	List p,q,r;
	if(L == NULL)
		return NULL;
	
	for(p=L; p != NULL; p = p->next->next) {
		q = (List) malloc(sizeof(struct linkedList));
		q->data = p->data;
		q->next = p->next;
		p->next = q;
	}
	for(p=L; p != NULL; p = p->next->next) {
		p->next->random = q->random->next;
	}
	q = r = L->next;
	for(p = L; p! = NULL; p = p->next) {
		p->next = p->next->next;
		q->next = q->next->next;
		q = q->next;
	}
	return r;
}