实验三： 有一个带头结点的双链表 L，设计一个算法将其所有元素逆置， 即第一个元素变为最后一个元素，第 2 个元素变为倒数第 2 个元 素，最后一个元素变为第 1 个元素。（课本例题 2.9）

算法如下：

1. 定义三个指针，分别指向当前节点、前驱节点和后继节点。
2. 将当前节点的后继节点指向前驱节点，前驱节点指向当前节点，当前节点指向后继节点。
3. 将前驱节点作为当前节点，后继节点作为下一个节点，重复步骤 2 直到遍历完整个链表。
4. 最后将头结点的后继节点和前驱节点交换，完成链表逆置。

代码实现如下（假设头结点为 head）：

// 定义三个指针
Node *pre = head, *cur = head->next, *next = nullptr;

// 将头结点的后继节点置为 nullptr，防止出现环
head->next = nullptr;

// 遍历链表并逆置
while (cur != nullptr) {
    // 获取当前节点的后继节点
    next = cur->next;
    // 将当前节点的后继节点指向前驱节点
    cur->next = pre;
    // 将前驱节点指向当前节点
    pre->prev = cur;
    // 将前驱节点作为当前节点
    pre = cur;
    // 将后继节点作为下一个节点
    cur = next;
}

// 将头结点的后继节点和前驱节点交换
head->prev = pre;
pre->next = head;
head = pre;

相关问题

有一个带头结点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，…，最后一个元素变为第1个元素。

在双链表中实现元素逆置的过程通常需要遍历整个列表并将每个节点的前驱指针和后继指针临时交换。以下是一个简单的步骤描述：

1. 定义两个指针，`prev` 和 `current`，初始化它们都为头结点 `L`（因为当前节点和前一个节点都是头结点本身）。

2. 创建一个临时指针 `temp`，用于存储 `current` 的后继节点。

3. 进行循环，直到 `current` 为 `null` 或者 `null`（表示链表结束）：
a. 将 `current` 的后继节点赋值给 `temp`。
b. 更新 `current` 的后继指针，使其指向 `prev`。
c. 移动 `prev` 和 `current` 向前，让 `prev` 现在指向 `temp`，`current` 指向下一个节点。

4. 当循环结束时，`prev` 就会变成新的头结点，因为它最后指向了原来的尾部。

下面是伪代码形式的实现：

function reverseList(L):
    prev = L
    current = L.next

    while current is not null:
        temp = current.next
        current.next = prev
        prev = current
        current = temp

    return prev  # 返回新头结点

c++有一个带头结点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，…，最后一个元素变为第1个元素。

在C++中，我们可以使用迭代或递归的方式实现将带头节点的双链表逆置。这里是一个基本的迭代方法：

struct ListNode {
    int val;
    ListNode *next;
    ListNode *prev; // 添加指向前一个节点的指针
};

// 函数用于交换两个节点的位置
void swapNodes(ListNode *&a, ListNode *&b) {
    if (a == nullptr || b == nullptr)
        return;
    
    // 临时存储a的下一个节点
    ListNode *temp = a->next;

    // 更新a和b的连接
    a->next = b;
    b->prev = a;

    // 如果b还有下一个节点，更新它们的连接
    if (b->next != nullptr)
        b->next->prev = a;

    a->next = temp; // 将a恢复到原来的位置，如果有的话
}

// 主函数逆置整个链表
void reverseList(ListNode *&head) {
    ListNode *current = head;
    ListNode *prev = nullptr;

    while (current != nullptr) {
        // 保存当前节点的下一个节点
        ListNode *nextTemp = current->next;

        // 逆序操作
        swapNodes(current, prev);

        // 更新当前和前一个节点
        current = nextTemp;
        prev = current; // 现在prev指向新的"当前"节点
    }
}

这个算法首先创建两个临时变量，一个存储当前节点的下一个节点，另一个作为临时存储位置。然后通过`swapNodes`函数交换当前节点和前一个节点的连接，并更新它们的指针。循环直到遍历完整个链表。