O(1) 时间删除环形链表中的某个结点

给定一个环形链表，为了便于处理，有一个头结点指向环中的某个结点，如图：

             d
          ↙    ↖
head -> a          c
          ↘    ↗
             b

要求实现功能：
输入一个结点的指针，在 O(1) 时间内删除对应的结点。假设待删除结点一定在该环形链表中。

算法思想：
如果直接删除指定的结点，需要知道它的前后两个结点的指针才能将删除后的链表串联起来。这样的时间复杂度是 O(n)。
但是我们可以把后面节点的值复制给想删除的节点，然后删除后面的结点，前后结点都可以很快得到。

代码实现：

#include <malloc.h>
#include <iostream>
using namespace std;

typedef struct LISTNODE {
    int val;
    struct LISTNODE *next;
} ListNode;

// 打印环形链表函数
void printList(ListNode *head) {
    if(head == nullptr || head->next == nullptr) return;

    ListNode *start = head->next;
    cout<<start->val<<endl;

    ListNode *p = start->next;
    while(p != start) {
        cout<<p->val<<endl;
        p = p->next;
    }
}

// 删除结点函数
void delNode(ListNode *head, ListNode *node) {
    if(node == nullptr) {
        return;
    }
    if(node->next == node) {
        head->next = nullptr;    // 赋成空, 否则使用 free() 会形成野指针
        free(node);
        return;
    }
    node->val = node->next->val;
    ListNode *tmp = node->next;    // 暂存待删除结点
    node->next = tmp->next;
    free(tmp);
}

int main()
{
    // 测试用例
    ListNode *a = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode *b = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode *c = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode *d = (ListNode*)malloc(sizeof(ListNode)); 
    a->val = 1;
    b->val = 2;
    c->val = 3;
    d->val = 4;
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = a;
    
    ListNode *head = (ListNode*)malloc(sizeof(ListNode)); 
    head->next = a;
    head->val = 0;
    
    // 打印链表 
    cout<<"Before:"<<endl;
    printList(head);    // 1 2 3 4
    
    // 删除节点 
    delNode(head, a);
    
    cout<<"After:"<<endl;
    printList(head);    // 2 3 4
    
    return 0;
}