线性表元素逆置reverse函数

线性表的元素逆置通常是指将线性表中的元素顺序反转。在计算机科学中，这可以通过各种数据结构如数组、链表等来实现。对于数组，可以创建一个新的数组存储原数组的倒序元素；对于链表，可以采用迭代或递归的方式遍历链表，并更新节点的指针，使其指向前一个节点而不是下一个节点。

以下是几种常见的逆置操作：

1. 数组逆置：通过两指针，一个从头开始，一个从尾开始，交换它们指向的元素，然后两个指针分别向中间移动，直到相遇。

2. 链表逆置：对单链表而言，可以设置三个指针，第一个指向当前节点，第二个指向下一个节点，第三个保存第二个节点的指针，然后依次调整这三个指针，使得当前节点的next指向前一个节点，直到遍历完整个链表。

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

# 对于链表：
def reverse_linked_list(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

相关问题

【问题描述】编写程序，将线性表元素序列逆置。要求线性表采用单链表存储结构，元素为int型。从键盘输入线性表元素，创建单链表，输入0结束，对线性表序列进行逆置，输出逆置前和逆置后的序列。

在C++中，你可以通过以下几个步骤编写一个简单的程序来实现这个功能：

1. 首先，你需要定义一个Node结构体作为单链表的节点，包含一个整数值和指向下一个节点的指针。

struct Node {
    int data;
    Node* next;
};

2. 创建一个函数来插入新的元素到链表的末尾，并保持链表的顺序。

void insert(Node** head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;

    if (*head == nullptr) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}

3. 编写一个函数用于链表的逆置，这通常涉及到三个指针，一个用于当前节点，一个用于前一个节点，另一个用于后续节点。

void reverseList(Node** head) {
    Node* prev = nullptr, *curr = *head, *next = nullptr;
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

4. 主函数中获取用户输入并调用上述函数，然后分别打印逆置前和逆置后的链表。

int main() {
    Node* head = nullptr;
    
    int input;
    std::cout << "请输入链表元素（输入0结束）：" << std::endl;
    while (std::cin >> input && input != 0) {
        insert(&head, input);
    }

    std::cout << "原链表序列：";
    printList(head);

    reverseList(&head);
    std::cout << "逆置后的链表序列：";
    printList(head);

    return 0;
}

// 辅助函数：打印链表
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << "\n";
}

当运行这个程序时，它会提示用户输入链表元素，结束后会显示原始链表和逆置后的链表。

试分别以顺序表和单链表作存储结构，各编写一个实现线性表就地逆置的算法

顺序表的就地逆置（即不需要额外空间）可以使用两个指针交换的方式来实现，从头和尾开始双向推进。以下是C++的实现：

void reverse_seq_list(SeqList& list) {
    int start = 0; // 指向第一个元素
    int end = list.size() - 1; // 指向最后一个元素

    while (start < end) {
        std::swap(list[start], list[end]);
        start++;
        end--;
    }
}

这里假设`SeqList`是一个自定义的顺序表类型，包含一个`size()`函数获取当前元素个数以及`swap`方法用于交换元素。

对于单链表，由于单链表无法直接访问其前驱节点，我们需要临时创建一个新的链表来实现逆置。以下是C++的链表版本：

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

void reverse_link_list(ListNode*& head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* nextTemp;

    while (curr != nullptr) {
        nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }

    head = prev;
}

这个函数接受链表头指针，并通过不断更新`prev`, `curr`和`nextTemp`指向，实现了链表的逆置。