显示链接列表时颠倒顺序

Question

我有这个代码，我从一开始就输入了5个随机元素1,3,5,7,9，然后我想显示我的链表（1,3,5,7,7,9），但由于一些奇怪的原因（9,7,5,3.1），它的顺序相反。你能指出问题吗？

#include <iostream> using namespace std;
struct node {
    int data;
    node * next; };
int n;
int main() {
    // input.
    cout << "please input 5 elements:n";
    node * head = NULL;
    for (int i = 0; i < 5; i++) {
        cin >> n;
        node * curr = new node;
        curr -> data = n;
        curr -> next = head;
        head = curr;
    }

    // display
    while (head) {
        cout << head -> data << "n";
        head = head -> next;
    }
    return 0;
}

Answer 1

实现这一点的一种方法是递归。使用调用堆栈来跟踪每个节点，您将继续遍历列表。到达末尾后，即可打印并结束函数。然后，这将向上传播到调用堆栈，将下一个元素打印回起点。

void print_revers(node* n)
{
    if (n)
        print_reverse(n->next)
    std::cout << n->data << std::endl;
}

此示例假设列表中next指向NULL或nullptr的最后一个节点

Answer 2

输入数据的每一步后，您的列表都是这样的：

1. 1
2. 3->1
3. 5->3->1
4. 7->5->3->1
5. 9->7->5->3->1

如果您想要列表（1、3、5、7、9），则需要将每个元素插入列表的末尾，而不是开头。因此，您需要有一个指向末尾的指针（我认为它被称为尾部）来按您想要的顺序放置元素。代码如下所示：

node * head = NULL, * tail = NULL;
for (int i = 0; i < 5; i++) {
    cin >> n;
    node * curr = new node;
    curr -> data = n;
    curr -> next = NULL;
    if(head == NULL) {
        head = tail = curr;
    }
    else {
        tail -> next = curr;
        tail = tail -> next;
    }
}

它应该这样工作。