Splitting a list with 2n nodes into two separate and equal lists

If the circular linked list has 10 nodes, then the two lists have 5 nodes each. The procedure for splitting a circular list with 2n nodes into two equal circular lists is given here:

# include <stdio.h>
# include <stdlib.h>
struct node 
{
	int data;
	struct node *link;
};
void split(struct node *p, struct node **q, int n) 
{
	struct node *temp;
	int i = 1;
	temp = p;
	while (i < n)
	{
		temp = temp->link;
		i++;
	}
	*q = temp->link;
	temp->link = p;
	temp = *q;
	while (temp->link != p)
		temp = temp->link;
	temp->link = *q;
}

struct node *insert(struct node *p, int n) 
{
	struct node *temp;
	/* if the existing list is empty then insert a new node as the
	 starting node */
	if (p == NULL) 
	{
		p = (struct node *) malloc(sizeof(struct node)); /* creates new node
		 data value passes
		 as parameter */

		if (p == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		p->data = n;
		p->link = p; /* makes the pointer point to itself because it is
		 a circular list*/
	} 
	else 
	{
		temp = p;
		/* traverses the existing list to get the pointer to the last node of
		 it */
		while (temp->link != p)
			temp = temp->link;
		temp->link = (struct node *) malloc(sizeof(struct node)); /*
		 creates new node using
		 data value passes as
		 parameter and puts its
		 address in the link field
		 of last node of the
		 existing list*/
		if (temp->link == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		temp = temp->link;
		temp->data = n;
		temp->link = p;
	}
	return (p);
}

void printlist(struct node *p) 
{
	struct node *temp;
	temp = p;
	printf("The data values in the list are\n");
	if (p != NULL)
		do 
		{
			printf("%d\t", temp->data);
			temp = temp->link;
		} while (temp != p);
	else
		printf("The list is empty\n");
}

int main() 
{
	int n, num;
	int x;
	struct node *start = NULL;
	struct node *start1 = NULL;
	printf("Enter the value of n \n");
	scanf("%d", &n);
	num = n;
	n *= 2;# include <stdio.h>
# include <stdlib.h>
struct node 
{
	int data;
	struct node *link;
};
void split(struct node *p, struct node **q, int n) 
{
	struct node *temp;
	int i = 1;
	temp = p;
	while (i < n)
	{
		temp = temp->link;
		i++;
	}
	*q = temp->link;
	temp->link = p;
	temp = *q;
	while (temp->link != p)
		temp = temp->link;
	temp->link = *q;
}

struct node *insert(struct node *p, int n) 
{
	struct node *temp;
	/* if the existing list is empty then insert a new node as the
	 starting node */
	if (p == NULL) 
	{
		p = (struct node *) malloc(sizeof(struct node)); /* creates new node
		 data value passes
		 as parameter */

		if (p == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		p->data = n;
		p->link = p; /* makes the pointer point to itself because it is
		 a circular list*/
	} 
	else 
	{
		temp = p;
		/* traverses the existing list to get the pointer to the last node of
		 it */
		while (temp->link != p)
			temp = temp->link;
		temp->link = (struct node *) malloc(sizeof(struct node)); /*
		 creates new node using
		 data value passes as
		 parameter and puts its
		 address in the link field
		 of last node of the
		 existing list*/
		if (temp->link == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		temp = temp->link;
		temp->data = n;
		temp->link = p;
	}
	return (p);
}

void printlist(struct node *p) 
{
	struct node *temp;
	temp = p;
	printf("The data values in the list are\n");
	if (p != NULL)
		do 
		{
			printf("%d\t", temp->data);
			temp = temp->link;
		} while (temp != p);
	else
		printf("The list is empty\n");
}

int main() 
{
	int n, num;
	int x;
	struct node *start = NULL;
	struct node *start1 = NULL;
	printf("Enter the value of n \n");
	scanf("%d", &n);
	num = n;
	n *= 2;
	/* this will create a circular list with 2n nodes*/
	while (n-- > 0) 
	{
		printf("Enter the data values to be placed in a node\n");
		scanf("%d", &x);
		start = insert(start, x);
	}
	printf("The created list is\n");
	printlist(start);
	split(start, &start1, num);
	printf("The first list is:\n");
	printlist(start);
	printf("The second list is:\n");
	printlist(start1);
	getchar();
	return 0;
}# include <stdio.h>
# include <stdlib.h>
struct node 
{
	int data;
	struct node *link;
};
void split(struct node *p, struct node **q, int n) 
{
	struct node *temp;
	int i = 1;
	temp = p;
	while (i < n)
	{
		temp = temp->link;
		i++;
	}
	*q = temp->link;
	temp->link = p;
	temp = *q;
	while (temp->link != p)
		temp = temp->link;
	temp->link = *q;
}

struct node *insert(struct node *p, int n) 
{
	struct node *temp;
	/* if the existing list is empty then insert a new node as the
	 starting node */
	if (p == NULL) 
	{
		p = (struct node *) malloc(sizeof(struct node)); /* creates new node
		 data value passes
		 as parameter */

		if (p == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		p->data = n;
		p->link = p; /* makes the pointer point to itself because it is
		 a circular list*/
	} 
	else 
	{
		temp = p;
		/* traverses the existing list to get the pointer to the last node of
		 it */
		while (temp->link != p)
			temp = temp->link;
		temp->link = (struct node *) malloc(sizeof(struct node)); /*
		 creates new node using
		 data value passes as
		 parameter and puts its
		 address in the link field
		 of last node of the
		 existing list*/
		if (temp->link == NULL) 
		{
			printf("Error\n");
			exit(0);
		}
		temp = temp->link;
		temp->data = n;
		temp->link = p;
	}
	return (p);
}

void printlist(struct node *p) 
{
	struct node *temp;
	temp = p;
	printf("The data values in the list are\n");
	if (p != NULL)
		do 
		{
			printf("%d\t", temp->data);
			temp = temp->link;
		} while (temp != p);
	else
		printf("The list is empty\n");
}

int main() 
{
	int n, num;
	int x;
	struct node *start = NULL;
	struct node *start1 = NULL;
	printf("Enter the value of n \n");
	scanf("%d", &n);
	num = n;
	n *= 2;
	/* this will create a circular list with 2n nodes*/
	while (n-- > 0) 
	{
		printf("Enter the data values to be placed in a node\n");
		scanf("%d", &x);
		start = insert(start, x);
	}
	printf("The created list is\n");
	printlist(start);
	split(start, &start1, num);
	printf("The first list is:\n");
	printlist(start);
	printf("The second list is:\n");
	printlist(start1);
	getchar();
	return 0;
}
	/* this will create a circular list with 2n nodes*/
	while (n-- > 0) 
	{
		printf("Enter the data values to be placed in a node\n");
		scanf("%d", &x);
		start = insert(start, x);
	}
	printf("The created list is\n");
	printlist(start);
	split(start, &start1, num);
	printf("The first list is:\n");
	printlist(start);
	printf("The second list is:\n");
	printlist(start1);
	getchar();
	return 0;
}

Consider a circular list containing 2n nodes, as shown in following Figure.

List containing 2n nodes

To split this list into two equal lists, it is required to traverse the list up to the nth node and store the link of the nth node, which is the address of (n+1)th node in the pointer, say q. After this, make the link field of the nth node point to the first node pointed to by p. Then traverse the list starting from the node pointed to by q up to the end. Then make the link field of the last node point to the node pointed to by q. The result of this is shown in following figure.

Splitting of a circular list.