cc150:實現一個算法來刪除單鏈表中間的一個結點，只給出指向那個結點的指針

cc150:實現一個算法來刪除單鏈表中間的一個結點，只給出指向那個結點的指針

實現一個算法來刪除單鏈表中間的一個結點，只給出指向那個結點的指針。

例子：

輸入：指向鏈表a->b->c->d->e中結點c的指針

結果：不需要返回什麼，得到一個新鏈表：a->b->d->e

解答

這個問題的關鍵是你只有一個指向要刪除結點的指針，如果直接刪除它，這條鏈表就斷了。 但你又沒辦法得到該結點之前結點的指針，是的，它連頭結點也不提供。在這種情況下， 你只能另覓他徑。重新審視一下這個問題，我們只能獲得從c結點開始後的指針， 如果讓你刪除c結點後的某個結點，那肯定是沒問題的。比如刪除結點d，那只需要把c 的next指針指向e，然後delete d就ok了。好的，如果我們就刪除結點d，我們將得到 a->b->c->e，和目標鏈表只差了一個結點。怎麼辦呢？把d的數據給c！ 結點結構都是一樣的，刪除誰都一樣，最關鍵的是結點中的數據，只要我們留下的是數據 a->b->d->e就OK了。

思路已經有了，直接寫代碼？等等，寫代碼之前，讓我們再簡單分析一 下可能出現的各種情況(當然包括邊界情況)。如果c指向鏈表的：1.頭結點；2.中間結點。 3.尾結點。4.為空。情況1，2屬於正常情況，直接將d的數據給c，c的next指針指向d 的next指向所指結點，刪除d就OK。情況4為空，直接返回。情況3比較特殊，如果c 指向尾結點，一般會認為直接刪除c就ok了，反正c後面也沒有結點了，不用擔心鏈表斷開。 可是真的是這樣嗎？代碼告訴我們，直接刪除c，指向c的那個結點(比如說b)的next指針 並不會為空。也就是說，如果你打印這個鏈表，它還是會打印出和原來鏈表長度一樣的鏈表， 而且最後一個元素為0！

關於這一點，原書CTCI中是這麼講的，這正是面試官希望你指出來的。然後， 你可以做一些特殊處理，比如當c是尾結點時，將它的數據設置為一些特殊字符， 這樣在打印時就可以不打印它。當然也可以直接不處理這種情況，原書裡的代碼就是這麼做 的。這裡，也直接不處理這種情況。

bool remove(node *c){
    if(c==NULL || c->next==NULL) return false;
    // if(c->next==NULL){//c為最後一個元素時直接刪除，不行，最後還是會打印出一個為0的結點，需要特殊處理
    //     delete c;
    //     return;
    // }
    node *q = c->next;
    c->data = q->data;
    c->next = q->next;
    delete q;
    return true;
}