编写算法逆置一个带头结点的双链表

算法步骤如下：

1. 如果链表为空或者只有一个节点，则直接返回原链表。
2. 定义三个指针p、q、r，分别指向头结点、第一个节点、第二个节点。
3. 将第一个节点的前驱指针和后继指针都置为空，作为逆置后的最后一个节点。
4. 依次将q节点的后继指向p节点，p节点的前驱指向q节点，r节点的前驱指向q节点，q节点的后继指向r节点。
5. 将p指针指向q节点，q指针指向r节点，r指针指向r节点的后继节点。
6. 如果r指针不为空，则重复执行步骤4和步骤5，直到r指针为空为止。
7. 将头结点的前驱指针置为空，将逆置后的最后一个节点的后继指针指向头结点，将头结点的后继指针指向逆置后的第一个节点。
8. 返回逆置后的链表。

以下是算法的C++实现代码：

struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode *p = head, *q = head->next, *r = q->next;
    p->next = NULL;
    while (r) {
        q->next = p;
        p->prev = q;
        r->prev = q;
        p = q;
        q = r;
        r = r->next;
    }
    q->next = p;
    p->prev = q;
    head->prev = NULL;
    head->next = q;
    return head;
}