面试题13：在O(1)时间删除链表结点

题目：

给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下：

class ListNode{
	int mNValue;
	ListNode mPNext;
}
public void deleteNode(ListNode pListHead,ListNode pToBeDeleted);
	

解题思路

解题思路：如果需要O(1)，则不能通过遍历找到该节点的前节点后，再删除该结点，因为这样的时间复杂度会是O(n)。可行的方法应该是将要删除的节点的下一个结点的值赋值为要删除的节点，然后将该下一个结点指向下下个结点，从而达到删除的效果。

注意：
1.考虑到要删除的结点可能位于链表的尾部或输入的链表只有一个结点的特殊情况。

2.还有如果不考虑时间复杂度情况下，最好要考一下要删除的结点是否存在链表中