删除链表的节点

在O(1)时间内删除链表节点

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

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

void DeleteNode(ListNode* head, ListNode* toBeDeleted);

思路：

如果待删除节点toBeDeleted有下一个节点next，则交换toBedeleted和next的value，然后删除next节点即可在O(1)时间内删除节点。如果没有下一个节点，则从头节点遍历到toBedeleted节点，然后删除toBedeleted节点。时间复杂度为O(1)，空间复杂度为O(1)

代码：

void DeleteNode(ListNode* head, ListNode* toBeDeleted) {
        if (head == nullptr || toBeDeleted == nullptr) {
            return;
        }
        //如果待删除节点有下一个节点，则交换后，删除下一个节点，否则遍历，然后删除
        if (toBeDeleted->next) {
            swap(toBeDeleted->value, toBeDeleted->next->value);
            ListNode* tmp = toBeDeleted->next;
            toBeDeleted->next = toBeDeleted->next->next;
            delete tmp;
            tmp = nullptr;
        }
        else {
            ListNode* dummyNode = new ListNode();
            dummyNode->next = head;
            ListNode* tmp = dummyNode;
            while (tmp->next && tmp->next != toBeDeleted) {
                tmp = tmp->next;
            }
            if (tmp->next) {
                ListNode* tmptmp = tmp->next;
                tmp->next = tmp->next->next;
                delete tmptmp;
                tmptmp = nullptr;
            }
        }
    }