Given LinkedList and K=2, N=41->2->3->4->5->6->7->8->9
so Partitioned LinkedList will be
1->2->3->4->5->6->7->8->9
Now delete first K nodes from each subpart and return linked list
3->4->7->8
Here first 2 nodes are deleted from each subparts.
Logic is simple
Keep counter to count occurrence of node in LinkedList
if Count<=K => delete this node.
But Practical its tricky
Solution
#include<stdio.h>
#include<iostream>
#include <stdlib.h>
using namespace std;
struct node
{
int data; //data belong to that node
node *next; //next pointer
};
void push(node **head, int data)
{
node *newnode = new node;
newnode->data = data;
newnode->next = *head;
*head = newnode;
}
void printList(struct node *head)
{
struct node *temp = head;
while (temp != NULL)
{
printf(“%d-> “, temp->data);
temp = temp->next;
}
//printf(“n”);
}
int deleteKafterN(struct node *head,int k, int n){
struct node *prev=NULL, *curr=NULL ,*temp =NULL;
int count=1;
prev=NULL;
curr=head;
printf(“nn=%d and k=%dn”,n,k);
//In Starting delete first K nodes and set Head.
for(int i=0;i<k;i++){
prev=head;
head = head->next;
free(prev);
count++;
}
if(head->next){prev=head;curr=head->next;count++;}
//Till next head of subLL increment pointers
while(count<n+1){
curr=curr->next;
prev=prev->next;
count++;
}
printf(“n”);
while(curr){
if(count == n+1){ count=1; }
if(count<=k){
prev->next=curr->next;
temp=curr;
curr=curr->next;
free(temp);
}
else {
prev=prev->next;
curr=curr->next;
}
count++;
}
//while
printList(head);
}
//deleteKafterN
int main()
{
node *head1 = NULL;
push(&head1, 60);
push(&head1, 50);
push(&head1, 40);
push(&head1, 30);
push(&head1, 20);
push(&head1, 10);
push(&head1, 9);
push(&head1, 3);
push(&head1, 1);
printList(head1);
deleteKafterN(head1,2,4);
return 0;
}
Working Code : http://ideone.com/Zt79kh
posted by Dhaval