程序员面试题精选100题(33)-在O(1)时间删除链表结点[数据结构] - 何海涛的日志 - 网易博客

程序员面试题精选100题(33)-在O(1)时间删除链表结点[数据结构] - 何海涛的日志 - 网易博客

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

我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。

上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是O(n)。

那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n，仍然为O(1)。

1.     public static void deleteNode(List list,Node nodeToDelete){  
2.         Node head=list.head;  
3.         if(head==null||nodeToDelete==null){  
4.             return;  
5.         }  
6.         if(head.next==null&&nodeToDelete==head){//Only one node in list and you happen to delete the node.  
7.             list.head=null;//head=null;-->wrong  
8.             return;  
9.         }  
10.         Node node=head;  
11.         if(node.next!=null&&nodeToDelete!=null){  
12.             Node mNode=nodeToDelete.next;  
13.             if(mNode!=null){  
14.                 Node nNode=mNode.next;  
15.                 nodeToDelete.data=mNode.data;  
16.                 nodeToDelete.next=nNode;  
17.             }else {//'nodeToDelete' is the last Node.  
18.                 Node previous=node;  
19.                 while(node.next!=null){  
20.                     previous=node;  
21.                     node=node.next;  
22.                 }  
23.                 previous.next=null;  
24.                 return;  
25.             }  
26.               
27.         }  

Read full article from 程序员面试题精选100题(33)-在O(1)时间删除链表结点[数据结构] - 何海涛的日志 - 网易博客