下边讨论暂不包括尾节点。
一般来说，我们要删除链表中的一个节点是需要知道其上一节点的。但我们真的需要吗？
其实我们可以将待删节点的下一节点的值和指向的下一节点赋予待删节点，然后删除待删节点的下一节点。具体示例程序如下：
1 //O(1)时间删除链表节点，从无头单链表中删除节点 2 void deleteRandomNode(Node *cur) 3 { 4 assert(cur != NULL); 5 assert(cur->next != NULL); //不能是尾节点 6 Node* pNext = cur->next; 7 cur->data = pNext->data; 8 cur->next = pNext->next; 9 delete pNext; 10 }
原文：http://www.cnblogs.com/xiehongfeng100/p/4604288.html