首页 > 代码库 > 每天一个小算法（4）----在O(1)时间删除指定结点

每天一个小算法（4）----在O(1)时间删除指定结点

2024-07-08 03:40:14   225人阅读

O(1)时间内删除结点的思路只能是复制该结点下一个结点的数据，然后删除该结点的下一个结点，来等效删除此结点。

需要注意的地方是删除头结点和尾结点的处理。

 1 #include <stdio.h> 2 #include <time.h> 3 #include <stdlib.h> 4 typedef struct Node 5 { 6     int data; 7     Node* next; 8 }Node, *List; 9 10 List createList(int num) //随机生成数字，构造链表11 {12     List aList = (List)malloc(sizeof(Node));13     aList->next = NULL;14     aList->data = http://www.mamicode.com/0;15     Node* qT = aList;16 17      // srand((int)time(0));18      for ( int i=0; i< num; ++i)19      {20          Node* pTN = (Node*)malloc(sizeof(Node));21          pTN->data = http://www.mamicode.com/rand()%100;22          pTN->next = NULL;23          qT->next = pTN;24          qT = pTN;25      }26      return aList;27 }28 29 void printList(List aList)    //打印链表30 {31     if ( aList == NULL || aList->next == NULL )32         return;33 34     Node* pT = aList->next;35     printf("element of list:\n\t");36     while( pT != NULL )37     {38         printf("%d ", pT->data);39         pT = pT->next;40     }41 42     printf("\n");43 }44 45 void deleteList(List aList)    //删除链表46 {}47 48 49 //删除结点主算法50 void deleteNode(List aList, Node* pNode)51 {52     if ( aList == NULL || pNode == NULL )53         return;54 55     if ( aList == pNode )56     {57         printf("refuse to delete head node\n");58         return;59     }60 61     if ( pNode->next == NULL )62     {63         Node* pT = aList->next;64         while ( pT->next != NULL )65         {66             pT = pT->next;67         }68 69         delete pNode;70         pT->next == NULL;71     }72 73     Node* pN = pNode->next;74     pNode->data = http://www.mamicode.com/pNode->next->data;75     pNode->next = pNode->next->next;76 77     delete pN;78 }79 80 int main(int argc, char const *argv[])81 {82      srand((int)time(0));83     List aList = createList(5);84     printList(aList);85     deleteNode(aList,aList->next->next);86     printList(aList);87     deleteList(aList);88     89     return 0;90 }

 


联系
我们