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

1. 定义一个指针p指向链表的最后一个结点。
2. 从最后一个结点开始，依次遍历链表，将每个结点的前驱结点和后继结点交换。
3. 遍历到头结点时，将头结点的前驱结点置为空，头结点的后继结点作为新的头结点。
4. 返回逆置后的链表头结点。

伪代码如下：

reverseList(head):
if head is null or head.next is null:
return head
p = head.next.prev
while p is not null:
temp = p.prev
p.prev = p.next
p.next = temp
p = p.prev
head.prev = null
head = head.next
head.prev.next = null
head.prev = null
return head

相关问题

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

算法步骤如下：

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;
}

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

以下是逆置一个带头结点的双链表的C++代码：

#include <iostream>

using namespace std;

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

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

int main() {
    ListNode* head = new ListNode(-1);
    ListNode* tail = head;
    for (int i = 1; i <= 5; i++) {
        ListNode* node = new ListNode(i);
        tail->next = node;
        node->prev = tail;
        tail = node;
    }
    
    cout << "Original list: ";
    ListNode* curr = head->next;
    while (curr != NULL) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    
    head = reverseList(head);
    
    cout << "Reversed list: ";
    curr = head->next;
    while (curr != NULL) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    
    return 0;
}

这里使用了双指针法，通过一个 `prev` 指针和一个 `curr` 指针来逆置链表。同时需要注意一些细节，比如链表头结点的处理和指针的赋值顺序等。