【剑指offer】面试题13：在O(1)时间删除出链表结点

2019-11-06 07:25:24

字体：大中小

来源：转载

供稿：网友

//题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点。//链表结点与函数的定义#include<iostream>struct ListNode{ int m_nValue; ListNode* m_pNext;};void DeleteNode(ListNode** pHead, ListNode* pToBeDeleted);void DeleteNode(ListNode** pHead, ListNode* pToBeDeleted){ if (pHead == NULL&*pHead == NULL) { return; } //要删除的结点不是尾结点(包括头结点但不是只有一个结点) 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 (*pHead == pToBeDeleted) { delete pToBeDeleted; pToBeDeleted = NULL; *pHead = NULL; } //链表有多个结点，删除尾结点 else { ListNode*pNode = *pHead; while (pNode->m_pNext != pToBeDeleted)//pNode为尾结点时，循环结束 { pNode = pNode->m_pNext; } pNode->m_pNext = NULL; delete pToBeDeleted; pToBeDeleted = NULL; }}

分析一下时间效率：对于(n-1)个非尾结点时间复杂度为O(1),对于尾结点来说，时间复杂度为O(n),因此总的平均时间复杂度是[(n-1)O(1)+O(n)]/n=O(1);

上一篇：《剑指Offer》面试题四之替换空格

下一篇：多维偏好分析