刪除結點的操作我們經常碰到，比如一個鏈表A->B->C->D->E->F->G。如果我們要刪除結點E，那么我們只需要讓結點D的指針指向結點F即可，但是我們現在只給出鏈表頭結點的指針以及結點E的指針，而又是單項鏈表，不能在O(1)時間內得到被刪除結點前面的那一個結點的指針，所以我們原先的方法是不能在O(1)時間內刪除結點E的。

那么既然我們不能獲得被刪除結點的前一個結點的指針，我們就需要轉變思路來考慮是否能夠用過被刪除結點后一個結點的指針來解決方法。因此被刪除結點E的后一個結點指針是很容易得到的，也就是E->m_pNext。

那么我們可能會想到如下方法：獲得F的指針，將F的數據賦值給E，然后讓E指向F的下一個結點。這里雖然刪除的是結點F，但是相當于刪除的是結點E。并且是O(1)時間復雜度。下面給出代碼實例：

#include<iostream> #include<stdlib.h> #include<stack> using namespace std;//鏈表結構 struct ListNode {int m_nValue;ListNode* m_pNext; };//創建一個鏈表結點 ListNode* CreateListNode(int value) {ListNode *pNode=new ListNode();pNode->m_nValue=value;pNode->m_pNext=NULL;return pNode;}//遍歷鏈表中的所有結點 void PrintList(ListNode* pHead) {ListNode *pNode=pHead;while(pNode!=NULL){cout<<pNode->m_nValue<<" ";pNode=pNode->m_pNext;}cout<<endl; }void ConnectListNode(ListNode* pCurrent,ListNode* pNext)//連接兩個結點 {if(pCurrent==NULL){cout<<"前一個結點不能為空"<<endl;exit(1);}else{pCurrent->m_pNext=pNext;} }void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted) {if(pToBeDeleted->m_pNext!=NULL)//如果要刪除結點后面還有結點{ListNode* pNext=pToBeDeleted->m_pNext;pToBeDeleted->m_nValue=pNext->m_nValue;pToBeDeleted->m_pNext=pNext->m_pNext;delete pNext;pNext=NULL;}else if(*pListHead==pToBeDeleted)//如果鏈表只有一個結點{delete pToBeDeleted;pToBeDeleted=NULL;*pListHead=NULL;}else//如果鏈表有多個結點，且刪除最后一個結點，那么只能遍歷鏈表{ListNode *pNode=*pListHead;while(pNode->m_pNext!=pToBeDeleted)pNode=pNode->m_pNext;pNode->m_pNext=NULL;delete pToBeDeleted;pToBeDeleted=NULL;} }void main() {//創建結點ListNode* pNode1=CreateListNode(1);//創建一個結點ListNode* pNode2=CreateListNode(2);//創建一個結點ListNode* pNode3=CreateListNode(3);//創建一個結點ListNode* pNode4=CreateListNode(4);//創建一個結點ListNode* pNode5=CreateListNode(5);//創建一個結點ListNode* pNode6=CreateListNode(6);//創建一個結點ListNode* pNode7=CreateListNode(7);//創建一個結點//連接結點ConnectListNode(pNode1,pNode2);//連接兩個結點ConnectListNode(pNode2,pNode3);//連接兩個結點ConnectListNode(pNode3,pNode4);//連接兩個結點ConnectListNode(pNode4,pNode5);//連接兩個結點ConnectListNode(pNode5,pNode6);//連接兩個結點ConnectListNode(pNode6,pNode7);//連接兩個結點//打印鏈表PrintList(pNode1);//打印//刪除結點DeleteNode(&pNode1,pNode3);//打印鏈表PrintList(pNode1);//打印system("pause");}

總結

以上是生活随笔為你收集整理的在O(1)时间删除链表结点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。