一天一道算法题---6.12---链表结点的删除

感谢微信平台---一天一道算法题---每天多一点进步--

problem:

　　给定链表的头指针和一个节点指针在O（1）时间删除该结点。链表结点的定义如下：

1 struct listNode
2 {
3     int m_nkey;
4     ListNode* m_pNext;
5 };
6 
7 void DeleteNode( ListNode* pListHead , ListNode* pToBeDeleted );

这题来头很大是goodle面试题...

对于链表我只写过几次.... 太渣了。。这边微信给出的分析很到位很好我将它贴上来

在链表中删除一个结点：--最常规做法

从链表的头结点开始顺序查找要删除的结点找到之后再删除由于是需要顺序查找时间复杂度O(n)

接下里是重点：　　

我们之所以需要从头结点开始查找要删除的结点是因为我们需要得到要删除的结点的前面一个结点。

我们试着换一种思路

我们可以从给定的结点得到它的下一个结点这个时候我们实际删除的是它的下一个结点由于我们已经得到实际删除的结点的前面一个结点因此完全是可以实现的

当然在删除之前我们需要把给定结点的下一个结点的数据拷贝到给定的结点之中此时时间复杂度O(1)

假设链表有n个结点这个算法在N-1下为O（1) 只有当给定的结点处于链表末端时为O(n)

那么平均o(X)为[ (n-1) * O(1)+O(n)]/n 仍然为O(1)

代码稍后贴出.... think

主要我要去洗澡了.......

晓爷说讲了一大串不知所云.... 那我来讲下我个人的理解.... 错误望留言提出 thanks

这里和我们一般删除结点有个很不一样的地方通常我们是根据要删除结点的数据来删除这个结点..

就是满足 value == node->data 然后才删掉这个node

然后我们删除一般是采用 “ 先连后断” 原则--- 假如 node = ptr->next 那么我们就让 ptr->next = node->next 然后delete node(如果是 C 就 free(node) ）

这样的话是O（n) 因为我们需要从head开始遍历整个链表直到找到满足数据相等的条件为止..

这里呢很特殊它直接告诉了我们要删除的结点指针注意这里是单链表.

这个方法真的很巧妙..

既然我们知道了要删除的结点指针那么我们肯定就知道了它的下一个结点通过node->next

我们可以选择让下一个结点的指针域和数据域来覆盖node结点的数据域和指针域然后 delete node->next 因为它的东西已经全 copy给了 node 这相当于做到了给 node的删除操作

这边有一个例外假如node是尾结点..此时node->next == NULL

so 遍历整个链表.....

end....

贴下微信给出的代码及注释

 1 // delete a node in a list
 2 //Input:  pListHead - the head of list
 3 //          pToBeDeleted - the node of to be deleted
 4 
 5 
 6 void DeleteNode( ListNode* pListNode , ListNode* pToBeDeleted )
 7 {
 8     if( !pListHead || !pToBeDeleted )
 9         return;
10     // if pToBeDeleted is not the last node in the list
11     if( pToBeDeleted->m_pNext!=NULL )
12     {
13         // copy data from the node to pToBeDeleted
14         ListNode* pNext = pToBeDeleted->m_pNext;
15         pToBeDeleted->m_nKey = pNext->m_nKey;
16         pToBeDeleted->m_pNext = pNext->m_pNext;
17         // delete the node next to the pToBeDeleted
18         delete pNext;
19         pNext = NULL;
20     }    
21     // if pToBeDeleted is the last node in the list
22     else
23     {
24         // get the node prior to pToBeDeleted
25         ListNode* pNode = pListNode;
26         while( pNode->m_pNext != pToBeDeleted )
27         {
28             pNode = pNode->m_pNext;
29         }
30         // delete pToBeDeleted;
31         pNode->m_pNext = NULL;
32         delete pToBeDeleted;
33         pToBeDeleted = NULL;
34     }
35 }

View Code

凌晨4点 4年

4年变了好多啊.......

又是4年....

下一个4年毕业了..

just follow your heart