CareerCup

Asuming node definition as

struct node
{
int data;
node *next;
};
My class definition is this way..

class linkedlist
{
public:
linkedlist();
void insertlast(const int);
void insertfirst(const int);
int deletelast();
int deletefirst();
int deletevalue(const int);
int deletenthlast(const int);
int lenght();
void print();
~linkedlist();
private:
node *first;
node *last;
};

Here is the code for deleting n-th node from last in linked list

int linkedlist::deletenthlast(const int n)
{
node *current,*previous=NULL,*nextnode=NULL;
int count=0,lenght=0;
current=first;

if(first==NULL)
{
cout<<"List is empty, no items to remove\n";
return 0;
}

current=first;
while(current!=NULL)
{
current=current->next;
lenght++;
}

current=first;

if(n>lenght)
{
cout<<"Requesting out of range element. Not possible\n";
return 0;
}
else if(n==lenght)
{

if(first==last && first!=NULL)
{
cout<<"Deleting the last item in the list\n";
first=NULL;
last=NULL;
return 0;
}
}
else if(n==1)
{
current=first;
while(current->next!=NULL)
{
previous=current;
current=current->next;
}
previous->next=NULL;
last=previous;
delete current;
return 0;
}
else
{
int i;
current=first;
count=lenght-n;
for(i=0;i<count;i++)
{
previous=current;
current=current->next;
nextnode=current->next;
}
previous->next=nextnode;
delete current;
return 0;
}
cout<<"End of method reached!!! This should not happen\n";
return 0;
}

I forgot to change the code according to the signature in the question... lemme know if someone needs it...

Pavankumar Bondugula

Guys..
There is one more clever way of doin it in one pass... this was given by my friend.. according to him..

start with 2 pointers at head and ptr1 stands at head and ptr2 moves 'n' nodes from head now move both the pointers with same speed until the ptr reahces the last node. now ptr1 points to the 'n'th node from last..delete it..

Pavankumar Bondugula.

Yup...Pavan that sol is in Programming interview exposed book :).

Here is the solution in one pass

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int value;
	node * next;
};

node * delete_kth(node *, int);
void main()
{
	int i, n1=0,n2=0,k=0,val = 0;
	node *temp, *head, *prev;
	printf("Enter the no. of nodes in the link list\n");
	scanf("%d", &n1);
	printf("Enter the values of the link list in order\n");
	scanf("%d", &val);
	head = (node *) malloc(sizeof(node));
	head->value = val;
	head->next = NULL;
	prev= head;
	for(i=1;i<n1;i++)
	{
		scanf("%d", &val);
		temp = (node *) malloc(sizeof(node));
		temp->value = val;
		temp->next = NULL;
		prev->next = temp;
		prev = temp;		
	}
	printf("Enter the value of the kth node from last that u wanna delete\n");
	scanf("%d",&k);
	if(k>n1 || k<=0)
		printf("Wong input\n");
	//Taking care of the boundary condition where you only have one node in the list
	else if(head->next == NULL)
			head = NULL;
		else
			head = delete_kth(head,k);
	temp = head;
	while(temp)
	{
		printf("%d ",temp->value);
		temp = temp->next;
	}
}
node * delete_kth(node *head, int k)
{
	int i;
	node *first, *temp, *future;
	temp = head;
	first = head;
	//If Head is NULL return
	if(!head)
		return NULL;
	for(int i =0;i<k;i++)
		temp = temp->next;
	//Taking care of the boundary  condition where k equals the length of the list
	if(!temp)
	{
		future = head;
		head = head->next;
		delete(future);
		return head;
	}		
	while(temp->next)
	{
		first = first->next;
		temp = temp->next;
	}
	future = first->next;
	first->next = future->next;
	delete(future);	
	return head;
}

One catch is that, given this kind of signature deleting the head node is difficult. The head pointer is just copied.
So I would ask the interviewer that ideally the signature being node* deleteNode(node** head, int n) would be fine. Else if its the head node to be deleted, I need to copy the next node's value to it and proceed.