如何在常数时间复杂度下高效删除链表节点（特定场景分析）

题目&＃xff1a;给定单向链表的头指针和一个结点指针&＃xff0c;定义一个函数在O&＃xff08;1&＃xff09;时间删除该结点。链表结点与函数的定义如下&＃xff1a;

struct ListNode
{int m_nValue;//数据域ListNode* m_pNext;//指针域
};void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);

分析&＃xff1a;

此题目若按照从前向后遍历寻找要删除的结点则需要O&＃xff08;n&＃xff09;的时间复杂度。

但是假设知道要删除的结点存在于链表中&＃xff0c;则思路可以转变为&＃xff1a;

1&＃xff09;要删除的结点的后面的结点值赋值给要删除的结点&＃xff0c;再把要删除结点的的下一个结点删除。

2&＃xff09;特殊情况1&＃xff1a;要删除的结点在链表的尾部&＃xff0c;则需要从头开始遍历&＃xff0c;因为尾结点的下一个结点不存在不能采用1&＃xff09;的步骤

3&＃xff09;要删除的结点位于头结点&＃xff0c;直接删除&＃xff0c;并赋NULL即可。

附图&＃xff1a;

参考&＃xff1a;【1】https://www.cnblogs.com/qingyuuu/p/4766320.html

参考代码&＃xff1a;

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{if (!pListHead || !pToBeDeleted)
return;if (pToBeDeleted->m_pNext !&＃61; NULL){ListNode* pNext &＃61; pToBeDeleted->m_pNext;pToBeDeleted->m_nValue &＃61; pNext->m_nValue;pToBeDeleted->m_pNext &＃61; pNext->m_pNext;delete pNext;pNext &＃61; NULL;}
//链表只有一个结点&＃xff0c;删除头结点&＃xff08;也是尾结点&＃xff09;else if(*pListHead &＃61;&＃61; pToBeDeleted){delete pToBeDeleted;pToBeDeleted &＃61; NULL;*pListHead &＃61; NULL;}
//要删除的结点是尾结点else{ListNode* pNode &＃61; *pListHead;while (pNode->m_pNext !&＃61; pToBeDeleted){pNode &＃61; pNode->m_pNext;}pNode->m_pNext &＃61; NULL;delete pToBeDeleted;pToBeDeleted &＃61; NULL;}
}


  参考&＃xff1a;【2】https://blog.csdn.net/wangfengfan1/article/details/46793755

【3】剑指