題目描述

• 給定單向鏈表的頭指針和一個(gè)節(jié)點(diǎn)指針，定義一個(gè)函數(shù)在 O(1) 時(shí)間內(nèi)刪除該節(jié)點(diǎn)
• 鏈表節(jié)點(diǎn)與函數(shù)的定義如下

struct ListNode{
    int  value;
    ListNode *next;
}

題目解讀

• 劍指Offer 119
• 把下一個(gè)節(jié)點(diǎn)的內(nèi)容復(fù)制到需要?jiǎng)h除的節(jié)點(diǎn)上覆蓋原有的內(nèi)容，再把下一個(gè)節(jié)點(diǎn)刪除

代碼

第二輪代碼是在第一輪代碼基礎(chǔ)上集合書(shū)上代碼修改的

• 第二輪代碼

#include<iostream>
using namespace std;

struct ListNode{
    int  value;
    ListNode *next;
};

// Print
void PrintList(ListNode *head){
    if(!head){
        cout<<"鏈表為空"<<endl;
    }
    else{
        while(head){
            cout<<head->value<<" ";
            head = head->next;
        }
        cout<<endl;
    }
}

ListNode* DeleteNode(ListNode *head, ListNode *toBeDelete){
    // 分三種情況
    // 1、欲刪除節(jié)點(diǎn)是首節(jié)點(diǎn)
    // 2、欲刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)(非首尾節(jié)點(diǎn))
    // 3、欲刪除節(jié)點(diǎn)是尾節(jié)點(diǎn)

    // 增強(qiáng)代碼魯棒性
    if(! head || ! toBeDelete){
        cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;
    }
    else{
        if(toBeDelete->next){ // 1、欲刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)(非首尾節(jié)點(diǎn))
            ListNode *temp;
            temp = toBeDelete -> next;
            toBeDelete->value = temp->value;
            toBeDelete->next = temp->next;
            delete temp;
        }
        else if(toBeDelete == head){ // 2、欲刪除節(jié)點(diǎn)是首節(jié)點(diǎn)
            delete toBeDelete;
            toBeDelete = NULL;
            head = NULL;
        }
        else{ // 3、欲刪除節(jié)點(diǎn)是尾節(jié)點(diǎn),此處需要判斷一下尾節(jié)點(diǎn)是否是toBeDelete
            ListNode *pre;
            ListNode *current;

            pre = head;
            current = pre->next;
            while(current->next){
                pre = current;
                current = pre->next;
            }

            if(current == toBeDelete){
                pre->next = NULL;
                delete current;
            }
        }
    }

    return head;
}

// Create
ListNode* createList(){
    // 運(yùn)行正確
    // int node[10] = {1, 2, 3, 3, 4, 4, 5};
    // int length = 7;
    
    // 驗(yàn)證只有一個(gè)節(jié)點(diǎn)的情況，通過(guò)
    int node[10] = {1};
    int length = 1;
    ListNode *head = NULL;
    ListNode *tail = NULL;

    for(int i=0; i < length; i++){
        ListNode *p = new ListNode();
        p -> value = node[i];
        p -> next  = NULL;

        if(!head){
            head = p;
            tail = head;
        }
        else{
            tail -> next = p;
            tail = p;
        }
    }
    // PrintList(head);
    return head;
}

int main(){
    ListNode *head;
    ListNode *toBeDelete;
    head = createList();
    // PrintList(head);  // 驗(yàn)證鏈表是否成功建立

    int todelete  = 1; // 此處設(shè)置刪除的位置
    for(int i=0; i < todelete; i++){
        if(i == 0){
            toBeDelete = head;
        }
        else{
            toBeDelete = toBeDelete->next;
        }
    }
    head = DeleteNode(head, toBeDelete);
    PrintList(head);
}

• 第一輪代碼

#include<iostream>
using namespace std;

struct ListNode{
    int  value;
    ListNode *next;
};

// Print
void PrintList(ListNode *head){
    if(!head){
        cout<<"鏈表為空"<<endl;
    }
    else{
        while(head){
            cout<<head->value<<" ";
            head = head->next;
        }
        cout<<endl;
    }
}

ListNode* DeleteNode(ListNode *head, ListNode *toBeDelete){
    // 分三種情況
    // 1、欲刪除節(jié)點(diǎn)是首節(jié)點(diǎn)
    // 2、欲刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)(非首尾節(jié)點(diǎn))
    // 3、欲刪除節(jié)點(diǎn)是尾節(jié)點(diǎn)

    // 增強(qiáng)代碼魯棒性
    if(! head || ! toBeDelete){
        cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;
    }
    else{
        // 1、欲刪除節(jié)點(diǎn)是首節(jié)點(diǎn)
        if(head == toBeDelete){
            // 又分兩種情況，鏈表是否只有一個(gè)節(jié)點(diǎn)
            // 鏈表只有一個(gè)節(jié)點(diǎn)
            if(! head->next){  // 此處有點(diǎn)小問(wèn)題，第二輪再修改！　即當(dāng)我這個(gè)函數(shù)無(wú)返回值時(shí)，此處無(wú)效
                head = NULL;
                PrintList(head);
            }
            else{ //鏈表有多個(gè)節(jié)點(diǎn)
                ListNode *temp;
                temp = toBeDelete -> next;
                toBeDelete->value = temp->value;
                toBeDelete->next = temp->next;
                delete temp;
            }
        }
        else if(toBeDelete->next){ // 2、欲刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)(非首尾節(jié)點(diǎn))
            ListNode *temp;
            temp = toBeDelete -> next;
            toBeDelete->value = temp->value;
            toBeDelete->next = temp->next;
            delete temp;
        }
        else{ // 3、欲刪除節(jié)點(diǎn)是尾節(jié)點(diǎn),此處需要判斷一下尾節(jié)點(diǎn)是否是toBeDelete
            ListNode *pre;
            ListNode *current;

            pre = head;
            current = pre->next;
            while(current->next){
                pre = current;
                current = pre->next;
            }

            if(current == toBeDelete){
                pre->next = NULL;
                delete current;
            }
        }
    }
    return head;
}

// Create
ListNode* createList(){
    // 運(yùn)行正確
    // int node[10] = {1, 2, 3, 3, 4, 4, 5};
    // int length = 7;
    
    // 驗(yàn)證只有一個(gè)節(jié)點(diǎn)的情況，通過(guò)
    int node[10] = {1};
    int length = 1;
    ListNode *head = NULL;
    ListNode *tail = NULL;

    for(int i=0; i < length; i++){
        ListNode *p = new ListNode();
        p -> value = node[i];
        p -> next  = NULL;

        if(!head){
            head = p;
            tail = head;
        }
        else{
            tail -> next = p;
            tail = p;
        }
    }
    // PrintList(head);
    return head;
}


int main(){
    ListNode *head;
    ListNode *toBeDelete;
    head = createList();
    // PrintList(head);  // 驗(yàn)證鏈表是否成功建立

    int todelete  = 1; // 此處設(shè)置刪除的位置
    for(int i=0; i < todelete; i++){
        if(i == 0){
            toBeDelete = head;
        }
        else{
            toBeDelete = toBeDelete->next;
        }
    }
    head = DeleteNode(head, toBeDelete);
    PrintList(head);
}

總結(jié)展望

• 熟悉鏈表刪除操作..