剑指Offer面试题13（java版）:在O(1)时间删除链表节点

Myth丶恋晨 2022-07-16 04:54 129阅读 0赞

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

在单向链表中删除一个节点，最常规的方法无疑是从链表的头结点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。

比如图a所表示的链表中，我们要删除节点i，可以从链表的头节点a开始顺序遍历，发现节点h的m\_PNext指向要删除的节点i，于是我们可疑把节点h的m\_PNext指向i的下一个节点即为j。指针调整之后，我们就可以安全地删除节点i并保证链表没有断开。这种思路由于需要顺序查找，时间复杂度自然就是O（n)了。

![Center][]

之所以要从头开始查找，是因为我们需要得到被删除的节点的前面一个节点。在单向链表中，节点中没有前一个节点的指针，所以只好从链表的头结点开始顺序查找。

那是不是一定要得到被删除的节点的前一个节点呢？答案是否定的。我们可疑很方面地得到要删除的节点的下一个节点。如果我们把下一个节点的内容复制到要删除的节点上覆盖原有的内容，再把下一个节点删除，那是不是就相当于把当前要删除的节点删除了？

我们还是以前面的例子来分析这种思路，我们要删除的节点i，先把i的下一个节点j的内容复制到i，然后把i的指针指向节点j的下一个节点。此时再删除节点j，其效果刚好是把节点i给删除了（图c)

上述问题还有一个问题；如果要删除的节点位于链表的尾部，那么它就没有下一个节点，怎么办？我们让然从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作。

最后需要注意的是，如果链表中只有一个节点，而我们又要 链表的头节点（也是尾节点），此时我们在删除节点之后，还需要把链表的头节点设置为NULL。

有了这种思路，现在我们是实现代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 在给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。 
3.   \*/  
4.  **package** swordForOffer;  
5.    
6.  **import** utils.ListNode;  
7.    
8.  /\*\* 
9.   \* @author JInShuangQi 
10.  \* 
11.  \* 2015年7月31日 
12.  \*/  
13. **public** **class** E13DeleteNodeInList \{  
14.     **public** **void** deleteNode(ListNode head,ListNode deListNode)\{  
15.         **if**(deListNode == **null** || head == **null**)\{  
16.             **return** ;  
17.         \}  
18.         **if**(head == deListNode)\{  
19.             head =**null**;  
20.         \}  
21.         **else**\{  
22.             **if**(deListNode.next == **null**)\{  
23.                 ListNode pinitListNode = head;  
24.                 **while**(pinitListNode.next.next != **null**)\{  
25.                     pinitListNode = pinitListNode.next;  
26.                 \}  
27.                 pinitListNode.next = **null**;  
28.             \}**else**\{  
29.                 deListNode.data = deListNode.next.data;  
30.                 deListNode.next = deListNode.next.next;  
31.             \}  
32.         \}  
33.     \}  
34. \}

平均复杂度为\[(n-1)\*O(1)+O(n)\]/n,结果还是O(1),符合面试官的要求。

[Center]: /images/20220716/ba05c3d7459a4d7e9a1ddcfb787002b1.png
[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47175249#