面試100 33使用o(1)的代價刪除給定的節(jié)點

   面試100  33使用O(1)的代價刪除給定節(jié)點

  一問題描述
       使用o(1)的代價刪除單鏈表中的某個節(jié)點，函數(shù)原型為 void deleteNode(ListNode * head , ListNode * deleteNode)
      最初的方法，刪除一個節(jié)點都為o(n)，因為需要從頭到尾的遍歷這個鏈表。
 
     但是該題目要求，必須用O(1)的代價，實現(xiàn)刪除操作。
     所以考慮直接刪除deleteNode節(jié)點之后的那個節(jié)點，但是刪除之前，需要把之后的那個節(jié)點的值，
      copy到deleteNode節(jié)點中，然后再執(zhí)行刪除操作。
 
     另外需要注意的是，當(dāng)deleteNode的后節(jié)點為空時，需要從頭遍歷進行刪除。此時操作的時間復(fù)雜度為o(n)，但是總的平均復(fù)雜度為
     O(n-1 + n) / n，結(jié)果仍然是O(1)。
    二 代碼如下：
     

void deletes(ListNode * head , ListNode * deleteNode) 
 {
   if(!head || !deleteNode) 
     return ;
   if(deleteNode->next)  //如果預(yù)刪除的節(jié)點有后節(jié)點，那么先將后節(jié)點的值，copy到deleteNode處，然后刪除其后節(jié)點 
   {
     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) //如果找到了預(yù)刪除的節(jié)點 
       {
          p->next = 0 ;
          delete deleteNode ;        
          deleteNode = 0 ;        
                  
       }     
   }        
 }

posted on 2011-05-21 20:11 kahn 閱讀(395) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關(guān)