Deepak Garg
BAN USERnode* skipMDeleteN(node* head, int m, int n)
{
if(head == NULL)
{
printf("\nList is empty");
getch();
return head;
}
if(length(head)<m)
{
printf("\nlenght of the list is less than m");
getch();
return head;
}
if(m == 0 && n == 0)
return head;
if(m == 0 && n > 0)
return NULL;
node* current = head;
node* prev = NULL;
int counter = 0;
while(current != NULL && counter < m)
{
//skip m element
prev = current;
current = current->link;
counter++;
}
counter = 0; //reset counter
node* temp = NULL;
while(current != NULL && counter < n)
{
temp = current;
current = current->link;
temp->link = NULL;
free(temp);
counter++;
}
prev->link = skipMDeleteN(current,m,n);
return head;
}
This is working code and covers almost all the cases and boundries:
void kSwap(node** head)
{
clrscr();
if(*head == NULL)
{
printf("\nlist is empty");
getch();
return;
}
if((*head)->link == NULL)
{
printf("\nList has only one element");
getch();
return;
}
printf("Enter the value of k: ");
int k;
scanf("%d",&k);
if(k<=0)
{
printf("\n K cannot be less than 1. Please try again");
getch();
kSwap(&(*head));
}
int len = length(*head);
if(k>len)
{
printf("\n value of k cannot be larger than the length of list.\n please try again");
getch();
kSwap(&(*head));
}
node* startNode = *head;
node* endNode = *head;
int data=0;
if(len%2 == 1 && (len+1)/2 == k) //list has odd number of elements and we are trying to swap middle one.
{
printf("\nswapping the same element");
getch();
return;
}
if(len == 2)//only two elements so either k=1 or k=2, elements will be swapped
{
data = startNode->data;
startNode->data = startNode->link->data;
startNode->link->data = data;
return;
}
int start = 2;
int end = 2;
while(start<k)//moving start pointer just one node before the actual node
{
startNode = startNode->link;
start++;
}
while(end<len+1-k)//moving the end pointer just one node before the actual node
{
endNode = endNode->link;
end++;
}
if(k == 1)//handling the extreme corner case when k=1 because it involve header manipulation
{
data = endNode->link->data;
endNode->link->data = startNode->data;
startNode->data = data;
return;
}
else if(k == len)//handling the extreme corner case when k=length because it involve header manipulation
{
data = endNode->data;
endNode->data = startNode->link->data;
startNode->link->data = data;
return;
}
else
{
data = startNode->link->data;
startNode->link->data = endNode->link->data;
endNode->link->data = data;
return;
}
}
Every linked list has a start node given. Mark this start node and reverse the complete linked list. if you still can reach to the start from this reversed list then there is a cycle. But how to reverse a linked list need to be found out? ;)
- Deepak Garg May 30, 2012