面试100 33使用o(1)的代价删除给定的节点

   面试100  33使用O(1)的代价删除给定节点

  一问题描述
       使用o(1)的代价删除单链表中的某个节点，函数原型为 void deleteNode(ListNode * head , ListNode * deleteNode)
      最初的方法，删除一个节点都为o(n)，因为需要从头到尾的遍历这个链表。
 
     但是该题目要求，必须用O(1)的代价，实现删除操作。
     所以考虑直接删除deleteNode节点之后的那个节点，但是删除之前，需要把之后的那个节点的值，
      copy到deleteNode节点中，然后再执行删除操作。
 
     另外需要注意的是，当deleteNode的后节点为空时，需要从头遍历进行删除。此时操作的时间复杂度为o(n)，但是总的平均复杂度为
     O(n-1 + n) / n，结果仍然是O(1)。
    二 代码如下：
     

void deletes(ListNode * head , ListNode * deleteNode) 
 {
   if(!head || !deleteNode) 
     return ;
   if(deleteNode->next)  //如果预删除的节点有后节点，那么先将后节点的值，copy到deleteNode处，然后删除其后节点 
   {
     ListNode * temp = deleteNode->next ;
     deleteNode->data = temp->data ;
     deleteNode->next = temp->next ;                  
     delete temp ;
     temp = 0 ;                  
                                             
   } 
   else
   {
       ListNode * p = head->next ;
       while(p->next != deleteNode)  
       {
         p = p->next ;
                       
       }
       if(p->next == deleteNode) //如果找到了预删除的节点 
       {
          p->next = 0 ;
          delete deleteNode ;        
          deleteNode = 0 ;        
                  
       }     
   }        
 }

posted on 2011-05-21 20:11 kahn 阅读(362) 评论(0)  编辑 收藏 引用 所属分类: 算法相关