首页 > 代码库 > 如何在O(1)的时间里删除单链表的结点

如何在O(1)的时间里删除单链表的结点

2024-07-15 09:46:24   223人阅读

题目是这样的：给你一个单链表的表头，再给你其中某个结点的指针，要你删除这个结点，条件是你的程序必须在O(1)的时间内完成删除。

由于有的同学对链表还不是很熟悉，本文尽量描述的通俗易懂，老鸟请直接跳过前面一大段。

链表结构如下：

[cpp] view plaincopyprint?
  1. struct node  
  2. {  
  3.     int val;  
  4.     node* next;  
  5. };  


题目不是很难，很快就能想到好办法：)

首先回顾一下普通的删除方法，首先通过表头，找到待删除结点（设为B）的前一个结点（设为A），将A的指向改一下就行，然后删除掉B结点就行了。要删除的结点一定要delete掉，这不仅是个好习惯，而且能避免将来项目中可能造成的内存泄露的严重问题。

[cpp] view plaincopyprint?
  1. void DeleteNode_On(node *LinkList, node *p)  
  2. {  
  3.     printf("delete:%d\n", p->val);  
  4.     node *s = LinkList;  
  5.     while(s->next != p)  
  6.         s = s->next;  
  7.     s->next = s->next->next;  
  8.     delete(p);  
  9. }  

这个算法主要耗时在于查找前一个结点，所以是O(n)的算法。

那么既然要求是O(1)，显然不能再去for一遍了，联想到数组的删除，这个问题就比较好解决了。

首先我们很容易就能得到待删除结点，即B结点的后一个结点C，然后将C的值赋值给B结点的值，相当于数组删除时候的覆盖，现在B结点和C结点一模一样了，接下来就相当简单了吧，我们不删B，直接利用B删掉C就行了，方法简单，时间O(1)。


但是仔细想想这个算法有个很明显的缺陷，如果待删除结点是最后一个结点呢？这个时候似乎没有什么好的解决办法，只能老老实实的O(n)了。现在我们来看看平均时间复杂度：

符合题目要求。

 

[cpp] view plaincopyprint?
  1. void DeleteNode_O1(node *LinkList, node *p)  
  2. {  
  3.     printf("delete:%d\n", p->val);  
  4.     if(p->next != NULL) //如果p不是末尾结点, 则让后一个结点覆盖掉p, 然后删除后一个结点  
  5.     {  
  6.         p->val = p->next->val;  
  7.         node *tmp = p->next;  
  8.         p->next = p->next->next;  
  9.         delete(tmp);  
  10.     }  
  11.     else // 如果p是末尾结点, 则找到p的前一个结点然后正常删除  
  12.     {  
  13.         node *s = LinkList;  
  14.         while(s->next != p)  
  15.             s = s->next;  
  16.         s->next = s->next->next;  
  17.         delete(p);  
  18.     }  
  19. }  


最后附上完整测试代码：

 

[cpp] view plaincopyprint?
    1. #include<iostream>  
    2.   
    3. using namespace std;  
    4.   
    5. struct node  
    6. {  
    7.     int val;  
    8.     node* next;  
    9. };  
    10.   
    11. void CreateLinkList(node *LinkList)  
    12. {  
    13.     node *s = LinkList;  
    14.     for(int i = 0; i < 10; i++)  
    15.     {  
    16.         node *t = new node;  
    17.         t->val = i;  
    18.         t->next = NULL;  
    19.         s = s->next = t;  
    20.     }  
    22. }  
    23.   
    24. void ShowLinkList(node * LinkList)  
    25. {  
    26.     node *s = LinkList->next;  
    27.     while(s = s->next)  
    28.         printf("%d ", s->val);  
    29.     putchar(10);  
    30. }  
    31.   
    32. void DeleteNode_On(node *LinkList, node *p)  
    33. {  
    34.     printf("delete:%d\n", p->val);  
    35.     node *s = LinkList;  
    36.     while(s->next != p)  
    37.         s = s->next;  
    38.     s->next = s->next->next;  
    39.     delete(p);  
    40. }  
    41.   
    42. void DeleteNode_O1(node *LinkList, node *p)  
    43. {  
    44.     printf("delete:%d\n", p->val);  
    45.     if(p->next != NULL) //如果p不是末尾结点, 则让后一个结点覆盖掉p, 然后删除后一个结点  
    46.     {  
    47.         p->val = p->next->val;  
    48.         node *tmp = p->next;  
    49.         p->next = p->next->next;  
    50.         delete(tmp);  
    51.     }  
    52.     else // 如果p是末尾结点, 则找到p的前一个结点然后正常删除  
    53.     {  
    54.         node *s = LinkList;  
    55.         while(s->next != p)  
    56.             s = s->next;  
    57.         s->next = s->next->next;  
    58.         delete(p);  
    59.     }  
    60. }  
    61.   
    62. int main()  
    63. {  
    64.     node *LinkList = new node;  
    65.     CreateLinkList(LinkList);  
    66.     ShowLinkList(LinkList);  
    67.   
    68.   
    69.     node *p = LinkList->next;  
    70.     for(int i = 0; i < 3; i++)  
    71.         p = p->next;  
    72.     DeleteNode_On(LinkList, p);  
    73.     ShowLinkList(LinkList);  
    74.   
    75.   
    76.     p = LinkList->next;  
    77.     for(int i = 0; i < 8; i++)  
    78.         p = p->next;  
    79.     DeleteNode_O1(LinkList, p);  
    80.     ShowLinkList(LinkList);  
    81.   
    82.     p = LinkList->next;  
    83.     for(int i = 0; i < 4; i++)  
    84.         p = p->next;  
    85.     DeleteNode_O1(LinkList, p);  
    86.     ShowLinkList(LinkList);  
    87.     getchar();  
    88.     return 0;  
    89. } 


联系
我们