用O（1）时间，删除一个链表节点（3）

电玩女神 2022-06-09 08:18 128阅读 0赞

![Center][]

ListCommon.h,ListCommon.cpp依赖：

[链表基本操作的函数实现。（1）][1]

有这样一个问题，给定一个单向链表的头结点pHead和要删除的节点pDeleted，但是要求在O（1）时间完成。

可能先想到的就是从头结点往前遍历，找到要删除的节点pDeleted，这样就知道了它的前后节点，但是这样的时间是O（n）。

这里的思路是：

把pDeleted的下一个节点pNode1的值赋给pDeleted，同时让pDeleted指向pNode2，然后把pNode1删掉，pDeleted就不删了，这样就不用从头遍历了。

其中有2个特殊情况，1）整个链表只有一个节点，2）要删除的节点是尾节点，这两种情况要特殊处理。

DeleteListNode.cpp

#include <iostream>
    #include "ListCommon.h"
    using namespace std;
    
    void deleteListNode(ListNode** pHead, ListNode* pDeleted){
    	if(pHead == NULL || pDeleted == NULL){
    		return;
    	}
    
    	cout << "before delete node:"<<endl;
    	PrintList(*pHead);
    
    //删除的节点不是头结点，也不是尾节点
    	if(pDeleted->m_pNext != NULL){
    		ListNode* pNext = pDeleted->m_pNext;
    		pDeleted->m_nValue = pNext->m_nValue;
    		pDeleted->m_pNext = pNext->m_pNext;
    		delete pNext;
    		pNext = NULL;
    //删除的是头部节点，这时头结点就被改变了，所以这里的pHead是指向指针的指针。
            }else if(*pHead == pDeleted){
    		delete pDeleted;
    		pDeleted = NULL;
    		pHead = NULL;
    	}else{
    //删除的是尾部节点，先找到它的前一个节点，然后把这个pDeleted节点删掉。
                    ListNode* pNode = *pHead;
    		while(pNode->m_pNext != pDeleted){
    			pNode = pNode->m_pNext;
    		}
    		pNode->m_pNext = NULL;
    		delete pDeleted;
    		pDeleted =NULL;
    	}
    	
    	cout << "after delete node:"<<endl;
    	PrintList(*pHead);
    }
    
    int main(int argc, char* argv[]){
    	ListNode* pNode1 = CreateListNode(1);
    	ListNode* pNode2 = CreateListNode(2);
    	ListNode* pNode3 = CreateListNode(3);
    	ListNode* pNode4 = CreateListNode(4);
    	ListNode* pNode5 = CreateListNode(5);
    
    	ConnectListNodes(pNode1,pNode2);
    	ConnectListNodes(pNode2,pNode3);
    	ConnectListNodes(pNode3,pNode4);
    	ConnectListNodes(pNode4,pNode5);
    
    	deleteListNode(&pNode1,pNode3);
    }

测试结果:

PC:~/algorithm$ g++ ListCommon.cpp DeleteListNode.cpp -o DeleteListNode  
PC:~/algorithm$ ./DeleteListNode  
before delete node:  
print list begin ---  
1  
2  
3  
4  
5  
print list end  
after delete node:  
print list begin ---  
1  
2  
4  
5  
print list end

[Center]: /images/20220609/735d394216224d98955493897dcb31af.png
[1]: http://blog.csdn.net/lin20044140410/article/details/77658778