刪除鏈表的節點

02-12

刪除鏈表的節點

在給定頭節點的單向鏈表中，O(1)時間內刪除鏈表的指定節點。

思路：我們需要得到被刪除鏈表的前一個節點。

我們將指定節點的下一個節點內容複製到該節點，然後刪除下一個節點。

參考代碼：

root@gt:/home/git/Code# ./a.out 87653210root@gt:/home/git/Code# cat deleteNode.c #include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct listNode{ int value; struct listNode *next;}ListNode;void delNode(ListNode** phead,ListNode* pnode){ if(!phead || !pnode) return; if(pnode->next != NULL) { ListNode* ptmp = pnode->next; pnode->value = ptmp->value; pnode->next = ptmp->next; free(ptmp); ptmp = NULL; } else if(*phead == pnode) { free(pnode); *phead = NULL; pnode = NULL; } else { ListNode* ptmp = *phead; while(ptmp->next != pnode) ptmp = ptmp->next; ptmp->next = NULL; free(pnode); pnode = NULL; }}int main(){ ListNode* phead = NULL; for(int i = 0;i < 10;i++) { ListNode* pnewNode = malloc(sizeof(ListNode)); pnewNode->value = i; pnewNode->next = phead; phead = pnewNode; } ListNode* pnode = phead; ListNode* pOldHead = phead;; for(int i = 0;i < 5;i++) { pnode = pnode->next; } delNode(&phead,pnode); ListNode* ptmp = pOldHead; while(ptmp && ptmp->next) { ptmp = ptmp->next; printf("%d ",ptmp->value); } return 0;}