Deleting in a linked list

Given only 开发者_运维知识库a pointer to the node to be deleted , how do we delete the node in the linked list...?

The question is too ambiguous, and is likely that way for a reason (e.g. to spawn a conversation instead of test your actual knowledge of the data structure). They are likely expecting you to ask "Is this a doubly linked list or a singly linked list?" If it is a doubly linked list, its a simple matter:

curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete curr;

If it is a singly linked list, you must have the head node so you can find the previous node in the list. So they are likely expecting you to ask if you have a pointer to the head node. The pseudo-code would then be:

loop from head to end until test->next == curr
test->next = curr->next;
delete curr;

Alternatively, if you can modify the list (without the head node):

temp = curr->next;
curr->data = temp->data;
curr->next = temp->next;
delete temp;

Well, its just a trick.

Assuming curr is the address given, following would be the pseudo code:

to_delete = curr->next
curr->data = to_delete->data
curr->next = to_delete->next
delete to_delete

Essentially this just copies data and next pointer of next node in the list to the current node and deletes the next node.

I think it's almost impossible in singly-linked lists if you don't have any pointer to list head. You should always have a linked list head pointer.

In a standard linked list implementation, you have to modify the node that points to the node being deleted. To modify it, you have to find it first. If you have a pointer to the list head, or any element prior to the one being deleted, you can find it by traversing the list. If not, there's no general solution to this problem.

You could get out of the situation by modifying the definition of a linked list to mark deleted nodes somehow (say, with a boolean attribute deleted), and in turn modify list traversal to skip such nodes.

You have a pointer to that node (say, node N). Meaning, you have access on that node.
If that node has pointer to it's front node and it's back node, then simply point the back node to the front node. And the front node to the back of your node N.

To illustrate: 
step 1:
---> [ node ] ---> [ node ] ---> [ node ] ---> 
<--- [  M   ] <--- [  N   ] <--- [  O   ] <--- etc...

step 2:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <--- [node N] <--- [  O   ] <--- etc...

step 3:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <----------------- [  O   ] <--- etc...

                                    [ node ] ---> (still points to node O)
      (still points to node M) <--- [  N   ]

step 4:
just point Node N to NULL
                                    [ node ] ---> NULL
                          NULL <--- [  N   ]

result:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <----------------- [  O   ] <--- etc...

I have a solution if this is not the tail.

If it is a singly-linked list you just "swap" with the node next to yours and delete that one instead.

Assuming I have

struct Node
{
  T value;
   Node * next;
};

Solution would be something like:

void freeNode( Node * node )
{
   Node * next = node->next;
   if( next )
   {
      node->value = next->value;
      node->next = next->next;
      free( next ); 
   }
   // else I'm stuck!
}

The above sort of pseudo mix of C and C++.

If the node we have is the tail, and assuming that the tail is indicated by node->next == NULL, I cannot make the previous node into the tail so I cannot solve.