CareerCup

bool del(list*& head,int N)
{
if(!head||N<0)
return false;
int i=0;
list* curr=head;
while(curr!=curr->next)
{
if(i==N)
{
list* temp=curr;
curr->next->prev=curr->prev;
curr->prev->next=curr->next;
curr=curr->next;
free(temp);
i=0;
}
else
{
i++;
curr=curr->next;
}
}
head=curr;
return true;
}

int n;
scanf("%d",&n);

node* DelNode(node *ptr)
{
node *temp;
int i;

if(ptr == NULL) printf("Empty list!");

// if only 1 node is present
if(ptr->next == ptr) return ptr;

// go to the nth node
for(i=0 ; i<n ; i++) ptr = ptr->next;

temp = ptr;

ptr->prev = ptr->next;
ptr->next->prev = ptr->prev;
ptr = ptr->next;

free(temp);

DelNode(ptr);
}

An optimization:
In case we afford a travesal of the list to find out the number of nodes in the list (count) then, we neednt run the for loop till n.

i.e. if n=8 but we have just 6 node in all, then we can iterate only for n/count times.

n/count could be calculated iteratively till such time its value is <= 6.

For example: If n=1200 and count=6, then there is no point doing 1200/6 traversals.

Test cases:
1. Pass a null pointer
2. List with a missing/bad link in between
3. Test with large value for n

There are many more considerations you have to take into account.

- what happens to the Head pointer/Tail pointer if the node that it points to is being deleted.

Here is my code that seem to work in all the cases. Let me if not..

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int value;
	node * next;
	node *prev;
};
node * delete_nth_node_repeat(node * head, int k);
void main()
{
	int i, n=0,k = 0, val = 0;
	node *temp, *head, *prev;
	printf("Enter the no. of nodes in the link list\n");
	scanf("%d", &n);
	printf("Enter the values of the link list in order\n");
	scanf("%d", &val);
	head = (node *) malloc(sizeof(node));
	head->value = val;
	head->next = head;
	head->prev = head;
	prev= head;
	for(i=1;i<n;i++)
	{
		scanf("%d", &val);
		temp = (node *) malloc(sizeof(node));
		temp->value = val;
		temp->next = head;
		temp->prev = prev;
		prev->next = temp;
		prev = temp;		
	}
	head->prev = prev;
	printf("Enter kth element to be repeatedly deleted\n");
	scanf("%d", &k);	
	head = delete_nth_node_repeat(head,k);
	temp = head;
	printf("The value of the leftover node is \n");
	do
	{
		 printf("%d ", temp->value);
		 temp = temp->next;
	}while(temp != head);
}
node * delete_nth_node_repeat(node * head, int k)
{
	node * prev, * temp;
	int i;
	if(head == NULL)
		return NULL;
	if(k == 0)
		return head;
	while(head->next != head)
	{
		temp = head;
		for(i=0;i<k-1;i++)
			temp = temp->next;
		prev = temp->prev;
		prev->next = temp->next;
		temp->next->prev = prev;
		delete(temp);
		if(temp == head)
			head = prev->next;
	}
	return head;
}