How about shifting all the contents/data of the node up one and deleting the last node? ie, node->data = node->next->data, etc. One issue I could see with this is if the nodes are being tracked any other way. If all the node pointers are in an array or something, it could become useless since their contents have changed.

boolean removeNode(Node * p){ Node * temp; if (NULL == p){ return FALSE; } if (NULL == p.next) { // p is last element in list free(p) } else { // p is non-last element temp = p.next; p.value = temp.value; p.next = temp.next; free(temp); } return TRUE; } }

The above code has a bug. If p is the last element, and you free it, the element before it still points to this freed element, so when iterating through the list you'll access this freed memory while thinking there is valid data stored at that location.

class Problem3 { /* * Problem 3: Google interview question * Remove a node from a singly linked list without knowing the head node. * All you have is the node itself. * */ // Create another list to store the rest of the nodes SinglyLinkedList list = new SinglyLinkedList(); // O(n^2) for traversing and adding to the end to preserve list integrity public bool GoodLuck(Node node) { /* * Returns False if node is deleted or true if the node wasn't deleted * displays rest of list: if any */ // Tail : delete if (node.Next == null) { node = null; } else { // Get the next node Node current = node.Next; // Traverse the rest of the list while (current != null) { // Add to new linked list list.AddLast(current.Value); // update position current = current.Next; } // Delete node = null; // Display the rest of the list list.PrintToConsole(); } return node != null; } }

This is almost a trick question with no good answer in c++ and irrelevant in java.