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

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

链表结点与函数的定义如下：

1 struct ListNode
2 {
3 　　int val;
4 　　ListNode* next;
5 };

分析：如下图所示，假设要删除的结点为p结点，若直接删除p结点，则必须知道p的上一个结点，而查找p的上一个结点的时间复杂度为O(N)。可以交换p和p的下一个结点q的数据，然后直接删除q，这样便保证了时间复杂度为O(1)。需要注意的是p为尾结点的情况。这时只能顺序遍历链表并完成删除操作。

 1 ListNode * deleteNode( ListNode* head, ListNode* toBeDeleted)
 2 {
 3     if (head==NULL || toBeDeleted == NULL)
 4         return head;
 5     if (toBeDeleted->next!=NULL)
 6     {//删除的结点不是尾结点
 7         ListNode* q = toBeDeleted->next;
 8         toBeDeleted->val = q->val;
 9         toBeDeleted->next = q->next;
10         delete q;
11         q = NULL;
12     }
13     else
14     {
15         if (toBeDeleted == head)
16         {//删除的结点既是头结点也是尾结点
17             delete toBeDeleted;
18             head = NULL;
19             toBeDeleted = NULL;
20         }
21         else
22         {//删除的结点是尾结点不是头结点
23             ListNode* p = head;
24             while (p->next!=toBeDeleted)
25                 p = p->next;
26             p->next = NULL;
27             delete toBeDeleted;
28             toBeDeleted = NULL;
29         }
30     }
31     return head;
32 }

PS：上述代码存在一个问题，因为它基于一个假设：要删除的结点的确在链表中。我们需要O(N)的时间才能判断链表中是否包含某一结点。

受到O(1)时间的限制，我们不得不把确保结点在链表中的责任推给了函数的调用者。在面试的时候，可以和面试官讨论这个假设，以便让面试官觉得我们考虑问题非常全面。