题目描述

• 给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间内删除该节点
• 链表节点与函数的定义如下

struct ListNode{
    int  value;
    ListNode *next;
}

题目解读

• 剑指Offer 119
• 把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除

代码

第二轮代码是在第一轮代码基础上集合书上代码修改的

• 第二轮代码

#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、欲删除节点是首节点
    // 2、欲删除节点是中间节点(非首尾节点)
    // 3、欲删除节点是尾节点

    // 增强代码鲁棒性
    if(! head || ! toBeDelete){
        cout<<"输入有误，请重新输入"<<endl;
    }
    else{
        if(toBeDelete->next){ // 1、欲删除节点是中间节点(非首尾节点)
            ListNode *temp;
            temp = toBeDelete -> next;
            toBeDelete->value = temp->value;
            toBeDelete->next = temp->next;
            delete temp;
        }
        else if(toBeDelete == head){ // 2、欲删除节点是首节点
            delete toBeDelete;
            toBeDelete = NULL;
            head = NULL;
        }
        else{ // 3、欲删除节点是尾节点,此处需要判断一下尾节点是否是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(){
    // 运行正确
    // int node[10] = {1, 2, 3, 3, 4, 4, 5};
    // int length = 7;
    
    // 验证只有一个节点的情况，通过
    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);  // 验证链表是否成功建立

    int todelete  = 1; // 此处设置删除的位置
    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、欲删除节点是首节点
    // 2、欲删除节点是中间节点(非首尾节点)
    // 3、欲删除节点是尾节点

    // 增强代码鲁棒性
    if(! head || ! toBeDelete){
        cout<<"输入有误，请重新输入"<<endl;
    }
    else{
        // 1、欲删除节点是首节点
        if(head == toBeDelete){
            // 又分两种情况，链表是否只有一个节点
            // 链表只有一个节点
            if(! head->next){  // 此处有点小问题，第二轮再修改！　即当我这个函数无返回值时，此处无效
                head = NULL;
                PrintList(head);
            }
            else{ //链表有多个节点
                ListNode *temp;
                temp = toBeDelete -> next;
                toBeDelete->value = temp->value;
                toBeDelete->next = temp->next;
                delete temp;
            }
        }
        else if(toBeDelete->next){ // 2、欲删除节点是中间节点(非首尾节点)
            ListNode *temp;
            temp = toBeDelete -> next;
            toBeDelete->value = temp->value;
            toBeDelete->next = temp->next;
            delete temp;
        }
        else{ // 3、欲删除节点是尾节点,此处需要判断一下尾节点是否是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(){
    // 运行正确
    // int node[10] = {1, 2, 3, 3, 4, 4, 5};
    // int length = 7;
    
    // 验证只有一个节点的情况，通过
    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);  // 验证链表是否成功建立

    int todelete  = 1; // 此处设置删除的位置
    for(int i=0; i < todelete; i++){
        if(i == 0){
            toBeDelete = head;
        }
        else{
            toBeDelete = toBeDelete->next;
        }
    }
    head = DeleteNode(head, toBeDelete);
    PrintList(head);
}

总结展望

• 熟悉链表删除操作..