Skip to main content

Clone a linked list with next and random pointer in c

C program for Clone a linked list with next and random pointer. Here more information.

// Include header file
#include <stdio.h>
#include <stdlib.h>

// C Program
// Clone a linked list with next and random field

// Linked List Node
typedef struct LinkNode
{
	// Define useful field of LinkNode
	int data;
	struct LinkNode * next;
	struct LinkNode * random;
}LinkNode;
LinkNode * getLinkNode(int data)
{
	// Create dynamic memory of LinkNode
	LinkNode * me = (LinkNode * ) malloc(sizeof(LinkNode));
	if (me == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set node value
	me->data = data;
	me->next = NULL;
	me->random = NULL;
	return me;
}
typedef struct MyLinkedList
{
	// Define useful field of MyLinkedList
	struct LinkNode * head;
}MyLinkedList;

MyLinkedList * getMyLinkedList()
{
	// Create dynamic memory of MyLinkedList
	MyLinkedList * me = (MyLinkedList *) malloc(sizeof(MyLinkedList));
	if (me == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	me->head = NULL;
	return me;
}
// Add new node at the end of linked list
void insert(MyLinkedList * me, int value)
{
	// Create  node
	LinkNode * node = getLinkNode(value);
	if ((me->head == NULL))
	{
		me->head = node;
	}
	else
	{
		LinkNode * temp = me->head;
		// Find last node
		while (temp->next != NULL)
		{
			// Visit to next node
			temp = temp->next;
		}
		// Add node at last position
		temp->next = node;
	}
}
// Display linked list element
void display(MyLinkedList * me)
{
	if ((me->head == NULL))
	{
		printf("\nEmpty linked list\n");
		return;
	}
	LinkNode * temp = me->head;
	printf("\n ");
	while (temp != NULL)
	{
		if ((temp != me->head))
		{
			printf("--->");
		}
		if ((temp->random != NULL))
		{
			printf("%d(%d)",temp->data,temp->random->data);
		}
		else
		{
			printf("%d",temp->data);
		}
		temp = temp->next;
	}
	printf("-->NULL");
}
// Clone the linked list  with next and random field
LinkNode * cloneList(MyLinkedList * me)
{
	if ((me->head == NULL))
	{
		return NULL;
	}
	// Define some auxiliary variable
	LinkNode * temp = NULL;
	LinkNode * current = me->head;
	LinkNode * node = NULL;
	LinkNode * front = NULL;
	// Step 1
	// Create and combine clone node
	while (current != NULL)
	{
		//Get current node of actual linked list
		temp = current;
		// Create clone node
		node = getLinkNode(current->data);
		// Visit to next node
		current = current->next;
		// Connect clone node after actual node
		temp->next = node;
		// Binding this clone to next upcoming
		// nodes in actual linked list
		node->next = current;
	}
	// Start to actual linked list
	current = me->head;
	// Step 2
	// Set actual value of random field in clone linked list
	while (current != NULL && current->next != NULL)
	{
		// Clone list node
		node = current->next;
		if ((current->random != NULL))
		{
			// Set random node in clone linked list
			node->random = current->random->next;
		}
		// Visit to actual linked list next node
		current = node->next;
	}
	// Agian start to actual linked list
	current = me->head;
	// Step 3
	// Separate actual and clone linked list
	while (current != NULL)
	{
		node = current->next;
		if ((front == NULL))
		{
			// Get first node of clone linked list
			front = node;
		}
		current->next = node->next;
		current = current->next;
		if ((current != NULL))
		{
			node->next = current->next;
		}
		else
		{
			node->next = NULL;
		}
	}
	return front;
}
int main()
{
	// Test linked list
	MyLinkedList * list1 = getMyLinkedList();
	MyLinkedList * list2 = getMyLinkedList();
	// Create Normal linked list
	insert(list1, 5);
	insert(list1, 6);
	insert(list1, 1);
	insert(list1, 8);
	insert(list1, 7);
	/*
	   Simple linked list
	   5 → 6 → 1 → 8 → 7 → NULL
	   Set random node value
	   ╷───────────┐
	   │           │
	   │   ╷───────│───┐
	   ↓───│───╷   │   │
	   ↓   ↓   ↑   │   │
	   5 → 6 → 1 → 8 → 7 → NULL
	   │   │       ↑   │
	   └───│───────┘   │    
	       │           │
	       └───────────┘ 
	    5(8)-->6(7)-->1(5)-->8(5)-->7(6)-->NULL
	    Linked list with random field
	*/
	// 5-->8
	list1->head->random = list1->head->next->next->next;
	// 6-->7
	list1->head->next->random = list1->head->next->next->next->next;
	// 1 --> 5
	list1->head->next->next->random = list1->head;
	// 8 --> 5
	list1->head->next->next->next->random = list1->head;
	// 7 --> 6
	list1->head->next->next->next->next->random = list1->head->next;
	list2->head = cloneList(list1);
	printf("\n Actual Linked List");
	display(list1);
	printf("\n Clone Linked List");
	display(list2);
}

Output

 Actual Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL
 Clone Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment