[已解决]单链表逆置

yangzhixiaohuli

将单链表倒置，要求只利用原表的存储空间。

原单链表如下所示：图片.png

倒置后的单链表应为：

1.png

输入格式:
第一行输入n的值，表示单链表的元素个数。
第二行输入n个整数值，作为单链表的各元素值。

输出格式:
输出倒置后的单链表的各元素值，各元素值之间用空格分隔。

输入样例1:
4
2 4 6 8

输出样例1:
8 6 4 2

输入样例2:
7
1 3 5 7 9 11 13

输出样例2:
13 11 9 7 5 3 1

4
2 4 6 8
8 6 4 2

这题用C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-18 17:24:35

要在C++中实现单链表逆置，且只利用原链表的存储空间，可以通过指针操作来改变链表的节点指向。以下是一个简单的实现：

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    LinkedList() : head(nullptr) {}

    void append(int val) {
        if (!head) {
            head = new Node(val);
        } else {
            Node* temp = head;
            while (temp->next) {
                temp = temp->next;
            }
            temp->next = new Node(val);
        }
    }

    void reverse() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;
        
        while (current) {
            next = current->next;  // Save next
            current->next = prev;  // Reverse current node's pointer
            prev = current;        // Move pointers one position forward
            current = next;
        }
        head = prev;
    }

    void print() const {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) {
                std::cout << " ";
            }
            temp = temp->next;
        }
        std::cout << "\n";
    }
};

int main() {
    int n;
    std::cin >> n;
    LinkedList list;

    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        list.append(val);
    }

    list.reverse();
    list.print();

    return 0;
}

### 代码说明：
- **Node 结构体**：用于表示链表节点，包含数据和指针用于指向下一个节点。
- **LinkedList 类**：用于管理链表，包括添加新节点 (`append` 方法)、反转链表 (`reverse` 方法) 和打印链表 (`print` 方法) 的功能。
- **reverse 方法**：通过改变节点的指向来逆置链表，不需要额外的存储空间。
- **main 函数**：负责输入并调用上述功能进行链表处理。

通过这个程序，你可以输入链表长度和元素，然后得到逆置后的结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要在C++中实现单链表逆置，且只利用原链表的存储空间，可以通过指针操作来改变链表的节点指向。以下是一个简单的实现：

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    LinkedList() : head(nullptr) {}

    void append(int val) {
        if (!head) {
            head = new Node(val);
        } else {
            Node* temp = head;
            while (temp->next) {
                temp = temp->next;
            }
            temp->next = new Node(val);
        }
    }

    void reverse() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;
        
        while (current) {
            next = current->next;  // Save next
            current->next = prev;  // Reverse current node's pointer
            prev = current;        // Move pointers one position forward
            current = next;
        }
        head = prev;
    }

    void print() const {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) {
                std::cout << " ";
            }
            temp = temp->next;
        }
        std::cout << "\n";
    }
};

int main() {
    int n;
    std::cin >> n;
    LinkedList list;

    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        list.append(val);
    }

    list.reverse();
    list.print();

    return 0;
}

### 代码说明：
- **Node 结构体**：用于表示链表节点，包含数据和指针用于指向下一个节点。
- **LinkedList 类**：用于管理链表，包括添加新节点 (`append` 方法)、反转链表 (`reverse` 方法) 和打印链表 (`print` 方法) 的功能。
- **reverse 方法**：通过改变节点的指向来逆置链表，不需要额外的存储空间。
- **main 函数**：负责输入并调用上述功能进行链表处理。

通过这个程序，你可以输入链表长度和元素，然后得到逆置后的结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。