剑指offer——O(1)时间删除单链表节点

//为保证在O（1）时间删除，所以无法保证被删除的节点一定在链表中，因此就需要函数调用者保证

#include <iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int vvalue) :value(vvalue), next(NULL){}
    ~Node(){
        cout << "~Node()" << endl;
    }
};

void DeleteNode(Node*& head, Node* toBeDeleteNode)
{
    if (head == NULL || toBeDeleteNode == NULL)return;
    if (toBeDeleteNode->next != NULL){//被删除节点不是尾节点
        Node* nextNode = toBeDeleteNode->next;
        swap(toBeDeleteNode->value, nextNode->value);
        toBeDeleteNode->next = nextNode->next;
        delete nextNode;
        nextNode = NULL;
    }
    else if (toBeDeleteNode == head){//被删除节点是尾节点且是头结点
        delete toBeDeleteNode;
        toBeDeleteNode = NULL; head = NULL;
    }
    else{//被删除节点是尾节点且不是头结点
        Node* curNode = head;
        while (curNode->next != toBeDeleteNode){
            curNode = curNode->next;
        }
        curNode->next = NULL;
        delete toBeDeleteNode;
        toBeDeleteNode = NULL;
    }
}
int main()
{
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);
    Node* node7 = new Node(7);
    node1->next = node2; node2->next = node3;
    node3->next = node4;
    node4->next = node5; node5->next = node6; node6->next = node7;
    Node* head = node1; Node* toBeDeleteNode = node7;
    DeleteNode( head, toBeDeleteNode);
    Node* curNode = head;
    while (curNode != NULL){
        cout << curNode->value << " ";
        Node* tmpNode = curNode;
        curNode = curNode->next;
        delete tmpNode;
    }
    cout << endl;
    system("pause");
}

《完》

本文出自 “零蛋蛋” 博客，谢绝转载！

剑指offer——O(1)时间删除单链表节点

原文：http://lingdandan.blog.51cto.com/10697032/1908402