O(1)复杂度实现单链表的插入删除操作

算法思路：

插入:
插入是指在某个节点之前插入一个新的节点，由于要找到前置节点，所以时间复杂度是O(n)。怎样实现O(1)的插入呢？我们得换一种思维方式，肯定是不能找前置节点，但我们可以交换节点和待插入节点的值，这样前置节点的next指针值没变，但是指向的内存地址的值已经是新节点的值了。
删除:
思路和插入的思路基本一样，就是交换节点和他的next节点，但是如何next节点为NULL,得找到上一个节点。

Github上摘过来的代码：

class Node {
    public:
        int value;
        Node*   next;

        ~Node() {
        if (next != NULL) {
            delete next;
        }
        }

        /**
         * 与q交换内存值
         */
        void exchange(Node* q) {
        Node* tmp = new Node();
        memcpy(tmp, this, sizeof(Node));
        memcpy(this, q, sizeof(Node));
        memcpy(q, tmp, sizeof(Node));
        }

    };

    class NodeList {
    private:
        Node* head;

        /**
         * 找到p的前置节点
         */
        Node*find_pre(Node *p) {
        Node* l = head;

        while (l->next != p) {
            l = l->next;
        }

        return l;
        }

    public:
        NodeList() {
        head = new Node();
        head->value = 0;
        head->next = NULL;
        }

        ~NodeList() {
        Node* p = head;
        Node* q = NULL;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        }

        /**
         * 在链表末尾追加
         */
        void add(Node* p) {
        Node* q = find_pre(NULL);
        q->next = p;
        p->next = NULL;
        }

        /**
         * 在链表节点p之前插入q,这种实现的复杂度O(n)
         */
        void insert(Node* p, Node* q) {
        Node* l = find_pre(p);

        l->next = q;
        q->next = p;
        }

        /**
         * 在链表节点p之前插入q,这种实现的复杂度O(1)
         */
        void quick_insert(Node* p, Node* q) {
        p->exchange(q);
        p->next = q;
        }

        /**
         * 移除p，时间复杂度O(n)
         */
        void remove(Node* p) {
        Node* q = find_pre(p);
        q->next = NULL;
        delete p;
        }

        /**
         * 快速移除p，时间复杂度O(1)
         */
        void quick_remove(Node* p) {
        //最后一个节点，没办法，只能用慢删除
        if (p->next == NULL) {
            remove(p);
        }
        Node* q = p->next;
        p->exchange(p->next);
        delete q;
        }

    };