首页 > 代码库 > 用O(1)的时间复杂度删除单链表中的某个节点
用O(1)的时间复杂度删除单链表中的某个节点
给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode{ int m_nKey; ListNode* m_pNext;};
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);这是一道广为流传的Google面试题，考察我们对链表的操作和时间复杂度的了解，咋一看这道题还想不出什么较好的解法，但人家把题出在这，肯定是有解法的。一般单链表删除某个节点，需要知道删除节点的前一个节点，则需要O(n)的遍历时间，显然常规思路是不行的。在仔细看题目，换一种思路，既然不能在O(1)得到删除节点的前一个元素，但我们可以轻松得到后一个元素，这样，我们何不把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素。可见，该方法可行，但如果待删除节点为最后一个节点，则不能按照以上思路，没有办法，只能按照常规方法遍历，时间复杂度为O(n)，是不是不符合题目要求呢？可能很多人在这就会怀疑自己的思考，从而放弃这种思路，最后可能放弃这道题，这就是这道面试题有意思的地方，虽看简单，但是考察了大家的分析判断能力，是否拥有强大的心理，充分自信。其实我们分析一下，仍然是满足题目要求的，如果删除节点为前面的n-1个节点，则时间复杂度为O(1)，只有删除节点为最后一个时，时间复杂度才为O(n)，所以平均的时间复杂度为：（O(1) * (n-1) + O(n)）/n = O(1);仍然为O(1).下面见代码：
1 /* Delete a node in a list with O(1) 2 * input: pListHead - the head of list 3 * pToBeDeleted - the node to be deleted 4 */ 5 6 struct ListNode 7 { 8 int m_nKey; 9 ListNode* m_pNext;10 };11 12 void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)13 {14 if (!pListHead || !pToBeDeleted)15 return;16 17 if (pToBeDeleted->m_pNext != NULL) { 18 ListNode *pNext = pToBeDeleted->m_pNext;19 pToBeDeleted->m_pNext = pNext->m_pNext;20 pToBeDeleted->m_nKey = pNext->m_nKey;21 22 delete pNext;23 pNext = NULL;24 }25 else { //待删除节点为尾节点26 ListNode *pTemp = pListHead;27 while(pTemp->m_pNext != pToBeDeleted) 28 pTemp = pTemp->m_pNext;29 pTemp->m_pNext = NULL;30 31 delete pToBeDeleted;32 pToBeDeleted = NULL;33 }34 }
用O(1)的时间复杂度删除单链表中的某个节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。