CareerCup

How abt this,

1.use two pointers.
2.Place the first pointer pointing to the first element.
3.Move the second pointer K positions.
3.After Kth postion,for every 2nd pointer shift also shift the first one by a position from begining.
4.When the second pointer reaches the end of the list,you have the first one pointing to the node to be deleted.

I ws also stuck bfr Programmin Interviews Exposed helped me out.

This is a question from Programming Interviews Exposed...
This can be done in O(n) with very few lines of code..

Maintain 2 pointers pointing to the head initially..Increment first pointer k times.. After kth increment of first pointer, start incrementing the second pointer for every increment of the first pointer.

When first pointer reaches the end of the list... the second pointer would be pointing to the kth element from the end.

The un-optimized approach would be:

1. Traverse the entire list till the end and find out the 'count'
2. Start off again from the head node and reach the (count-k)th node and delete it


A better approach:

1. Use the 2-pointer method (one ptr traverses every node while the other moves a step ahead for every 2 traversals of the former ptr)

2. The faster pointer hits the tail of the list and the slower one is now poiting to the middle node

3. If (count-k) < ceil(count/2)
---> then start traversing from the head till you reach the (count-k)th node
else if (count-k) > ceil(count/2)
---> traverse from the mid element till you reach the (mid-k)th element and delete it
else if k == mid
---> delete mid and choose appropriately the new mid (pointer)

Can any more optimization be done?

I think both the solutions need atleast two traversals of the list.

So both are equally efficient.

My solution is

void deletekthnode(struct node * head,int k)
{
struct node * current,temp;
int count = 0;
for (current = head;current->next!= NULL;current = current->next)
count++;
count = count +1 -(k-1) //1 added to add the last node .

for(int i = 0,current = head;i<count;i++)
;
temp = current->next;
current->next = temp->next;
temp->next = NULL;

}

Here is my solution that requires only one traversal...

#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;
}