C++顺序表原地逆置算法

C++顺序表原地逆置算法可以通过交换顺序表中对应位置的元素来实现。具体实现如下：

void reverseList(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n / 2; i++) {
        swap(nums[i], nums[n - i - 1]);
    }
}

其中，`nums`为待逆置的顺序表，`n`为顺序表的长度。算法的时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

实验题目： 1 顺序表逆置算法 2 单链表的逆置算法 实验代码 实验结果

对于这两个实验题目，实验代码的具体编写会因使用的编程语言而异，以下是简要的示例说明：

1. **顺序表逆置算法（Python）**:

def reverse_array(arr):
    start, end = 0, len(arr) - 1
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1
    return arr

# 示例
original_array = [1, 2, 3, 4, 5]
reversed_array = reverse_array(original_array)

2. **单链表逆置算法（C++）**:

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr, *current = head;
    while (current != nullptr) {
        ListNode* next_temp = current->next;
        current->next = prev;
        prev = current;
        current = next_temp;
    }
    return prev;
}

实验结果通常会在运行上述代码并打印原始和处理后的数据结构后得出：

- 对于顺序表，你会看到数组元素是否按照预期进行了逆序。
- 对于单链表，观察前驱和后继指针的变化以及链表节点的新序列。

要得到详细的实验结果，你需要亲自运行代码并在控制台上查看输出，或者用特定的测试用例验证链表节点的顺序。

用c++实现算法，将顺序表A逆置，只允许在原表的存储空间外再增加一个附加的工作单元

在C++中，你可以使用双指针法实现顺序表A的逆置，而无需额外的存储空间。这里是一个简单的示例：

#include <iostream>

// 定义顺序表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 双指针逆序函数
void reverseList(ListNode** head, ListNode** tail) {
    if (*head == nullptr || *tail == nullptr) return; // 如果链表为空则直接返回

    // 将next指针暂时指向当前节点的下一个节点
    ListNode* temp = (*tail)->next;

    // 更新tail指向当前节点
    (*tail)->next = nullptr;

    // 遍历到倒数第二个节点，并更新头和尾
    while (temp != *head) {
        (*tail) = temp;
        temp = temp->next;
    }

    // 最后更新头指向原来尾部
    (*head) = *tail;
}

// 主函数测试
int main() {
    ListNode* A = new ListNode(1);
    A->next = new ListNode(2);
    A->next->next = new ListNode(3); // 假设A有三个元素

    ListNode* prevTail = nullptr; // 初始化前一个尾部为nullptr
    reverseList(&A, &prevTail); // 传入地址避免复制节点

    // 输出逆序后的列表
    ListNode* curr = A;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

    delete A; // 注意释放内存
    return 0;
}

在这个示例中，我们通过`prevTail`指针跟踪上一次的`tail`，每次循环都将`tail`向后移动一位，直到遍历完整个链表。最后`head`会指向原来的尾部，实现了逆序。