CareerCup

Copy the 4 to 3, and delete that node using the pointer pointing to 4 now (pointing to 3 before)..

How would you do this? Anyone?

node* temp = list->next;
if(temp){
list->value = temp->value;
list->next = temp->next;
delete temp;
}

You still have a tail don't you?

Assumption: a functon exists that updates the tail.

Algorithm:
1 -> 2 -> 3 -> 4 -> 5

Split the list
1 -> 2 <- temp tail
3 -> 4 -> 5 <- tail

1 -> 2 <-temp tail
4 -> 5 <- tail

1 -> 2 -> 4 -> 5.

The problem is how do you combine the two link lists in your final step with "temp tail" deleted and 2 point to 4?

1 -> 2 <-temp tail
4 -> 5 <- tail

1 -> 2 -> 4 -> 5.

You can't otherwise because there's no path to node 2.

so, jack, your method won't work.

By saying you don't have access to the head pointer doesn't preclude that a method exists to maintain the tail.

By saying you don't have access to the head pointer doesn't preclude that a method doesn't exists to maintain the tail.

What exactly does the interviewer mean by delete? Does this mean deleting the value of the node so it's not printed or deallocating the entire node?

The interviewer means "deleting the value so that the final linked list will be 1->2->4->5"..It doesn't matter which node (memory location) was deleted, to obtain this..
As I mentioned earlier, this is the algorithm to do it in constant time..
Lets say the pointer p is pointing to the node having value 3.
1. Copy the value in the next node (4) to the value in the node pointed to by p. (so now you have 1->2->4->4->5)
2. Delete the node next to the node pointed to by p (second 4) using normal node deletion method (yoyo has given the code for it)..This leaves us with the linked list (1->2->4->5).
This algorithm will not work if p is pointing to the last element in the linked list.

can anyone has a solution to solve this last node problem. We shd try to have some general soltion which can satisfy all the conditions.

The above solution works fine if you remove the conditional-if statement and state the assumption that the tail points to the head (a circular linked list). It is still a singly linked list.

PR's solution is the ONLY solution. I have come across the answer before.

Another solution, use memory copy to copy content of next node to the memory address of current node which is to be deleted. Then free the next node. It is impossible to handle last node case because previous node always points to some memory address where should not be null. So ...

PR's solution works, but I am wondering-
when you dont have the address of the head, how can you print:
1->2->4->5?

The pointer would be pointing to node 4, so at best you can print 4 and 5.

For the linked list 1->2->3->4->5,
First of all we presume that we know the structure of the node, i.e something like

Node
{ int i;
Node *p
}

If we assume that the pointer to node 3 is present in node 2 and not a copy of the pointer in node2,i.e.not a pointer present somewhere else is memory, then we know the pointer to node 2.This is because if the node contains integer values, each pointer is 4 bytes(?). So,in memory, node 2's value is present 4 bytes before node3 pointer because integer type pointer takes 4 bytes in memory adjacent to the integer value 2. Therefore, we now know the pointer to node 2 by subtracting 4bytes from the pointer to node3. Once we know the pointer to node2, we can try to find the pointer to node1. This can be done by trying to find the address of pointer(double pointer). Subtract 4bytes from the double pointer and you get the header of the linked list. From this we can do the trivial operations.

@Anand- When you actually write code for it it may seem to work. But it is not a very good thing to be doing this because if you are going to free a node (say node 5, for whatever reason) and then move on to insert one more (say before node 3) then the address of the memory allocated to this new node would that which was just free'd.

PS: This more depends on the platform on which you are running your code and how the OS implements dynamic memory allocation.

So, your solution may work in quite a few cases but not always.

@Payal- If you are reading this, what was the solution that you gave? What was the reaction of the interviewer?

I really could not see any other way of printing it without the head.

Now, as Sunil says, if we insert one more node before node3, say node 6, if we have to be consistent with the structure of the linked list i.e. 1->2->6->3->4, then we also have to modify the pointer from node6 to point to node3. Again, we can back track for double pointer from node3 itself to extract node6 address. This time, we can extract node6 address and then node2. We can still back track, can't we? HOWEVER, the thinking here is that the node6 which was created in place of node5(after node5's deletion) is still "in the link from node2" OTHERWISE, the linked list is broken, which means there is no point in maintaining the list further. The last point is important here. Please correct me if I am wrong.

Hold the node 4 with another pointer
Make the node 3 as 4
I mean copy the content in node 4 into node 3
delete node 4
Over.

Here is the code....

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

void deletenode(node *);
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 = NULL;
	prev= head;
	for(i=1;i<n;i++)
	{
		scanf("%d", &val);
		temp = (node *) malloc(sizeof(node));
		temp->value = val;
		temp->next = NULL;
		prev->next = temp;
		prev = temp;		
	}
	printf("Enter the node you wish to delete\n");
	scanf("%d",&k);
	temp = head;
	k = k-1;
	while(k--)
		temp = temp->next;
	//Taking care of the boundary condition where you only have one node in the list
	if(temp->next == NULL && temp == head) // If the linklist only has one node
		head = NULL;
	else if(temp->next == NULL && temp != head) //If last node in the list needs to be deleted
	{
		printf("Can't delete the last node\n");
		exit(0);
	}
	else if((temp->next != NULL && temp == head)) //If head needs to be deleted
		head = head->next;
	else
		deletenode(temp);
	temp = head;
	while(temp)
	{
		printf("%d ",temp->value);
		temp = temp->next;
	}
}
void deletenode(node *head)
{
	int i;
	node *first, *temp, *future;
	temp = head;
	first = head;
	//If Head is NULL return
	if(head)
	{	
		head->value = head->next->value;
		future = head->next->next;
		delete(head->next);
		head->next = future;
	}
}

This is just copy content problem.
We want to delete 3.

Check the pattern:
1 - 2 - 3 - 4 - 5

Copy value 0f 4 to 3
1 - 2 - 4 - 4 - 5

Copy value of 5 to 4
1 - 2 - 4 - 5 - 5

5 is the last, make it null

Now you have
1 - 2 - 4 - 5

Here is small algo:
node n = 3'rd node
while (n.next != null)
{
n.value = n.next.value;
}
n = null;

There is not need to copy all the numbers following that number.Copying only 4 to 3 and deleting 4 would do

p->data=p->right->data;
q=p->right;
p->right=q->right;
q=NULL;

This is very efficient when compared to the above solutions

But how to print all content link list without knowing head as mentioned in question...after doing deletion