Microsoft Interview Question
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
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;
}
bool del(list*& head,int N)
- winia October 26, 2008{
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;
}