题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点。
链表结点与函数的定义如下:
1 struct ListNode2 {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 else14 {15 if (toBeDeleted == head)16 { //删除的结点既是头结点也是尾结点17 delete toBeDeleted;18 head = NULL;19 toBeDeleted = NULL;20 }21 else22 { //删除的结点是尾结点不是头结点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)时间的限制,我们不得不把确保结点在链表中的责任推给了函数的调用者。在面试的时候,可以和面试官讨论这个假设,以便让面试官觉得我们考虑问题非常全面。