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

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

  一問(wèn)題描述
       使用o(1)的代價(jià)刪除單鏈表中的某個(gè)節(jié)點(diǎn)，函數(shù)原型為 void deleteNode(ListNode * head , ListNode * deleteNode)
      最初的方法，刪除一個(gè)節(jié)點(diǎn)都為o(n)，因?yàn)樾枰獜念^到尾的遍歷這個(gè)鏈表。
 
     但是該題目要求，必須用O(1)的代價(jià)，實(shí)現(xiàn)刪除操作。
     所以考慮直接刪除deleteNode節(jié)點(diǎn)之后的那個(gè)節(jié)點(diǎn)，但是刪除之前，需要把之后的那個(gè)節(jié)點(diǎn)的值，
      copy到deleteNode節(jié)點(diǎn)中，然后再執(zhí)行刪除操作。
 
     另外需要注意的是，當(dāng)deleteNode的后節(jié)點(diǎn)為空時(shí)，需要從頭遍歷進(jìn)行刪除。此時(shí)操作的時(shí)間復(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é)點(diǎn)有后節(jié)點(diǎn)，那么先將后節(jié)點(diǎn)的值，copy到deleteNode處，然后刪除其后節(jié)點(diǎn) 
   {
     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é)點(diǎn) 
       {
          p->next = 0 ;
          delete deleteNode ;        
          deleteNode = 0 ;        
                  
       }     
   }        
 }

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