C中的反向遍历单链表

Question

最近在一次采访中被问到这个问题。我所能做的就是从一个从0到9开始的链表从9到1遍历。这是代码：

 #include <iostream>

typedef struct node {
      int data;               // will store information
      node *next;             // the reference to the next node
};
node *head;

int printList(node *traverse) {
    if (traverse->next == NULL) {
        return -1;
    }
    traverse=traverse->next;
    printList(traverse);

    cout << traverse->data << endl;
    return 0;
}

int main() {
    node *temp = NULL;
    node *begin = NULL;
    for (int i = 0; i < 10; i++) {
        temp = new node;
        temp->data = i;
        if (begin == NULL) {
            begin = temp;
        }
        if (head != NULL) {
            head->next = temp;
        }
        head = temp;
        head->next = NULL;
    }
    head = begin;
    printList(head);
    return 0;
}

1. 如何使用 printList() 递归函数打印 0（第一个元素）？

2. 如何用 while 循环替换 printList() 递归函数？

3. 如果在采访中被问到， main() 函数是否有正确的节点初始化和插入？

原文由 Sarp Kaya 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

它们是实现这一目标的四种可能方法，每种方法都有其优点。

递归

void print_list(node* traverse)
{
    if (traverse == NULL) return;
    print_list(traverse->next);
    std::cout << traverse->data << std::endl;
}

这可能是第一个想到的答案。但是，进程堆栈大小是有限的，因此递归的限制非常低。一个大列表会引发堆栈溢出。这在 C++ 中不是一个很好的设计。

迭代

void print_list(node *n)
{
    using namespace std;
    deque<node*> res;
    for(;n != NULL; n = n->next) res.push_back(n);
    for_each(res.rbegin(), res.rend(), [](node* n){cout << n->data << endl;});
}

当然，如果你想让它成为迭代方式，你需要自己堆叠节点指针（在进程堆上），而不是将这个作业委托给 _调用堆栈_。此方法可让您打印更大的列表，并且计算时间为 O(n)。但是，它的内存使用量为 O(n)，但您已经有一个使用 O(n) 内存的列表。所以这应该不是问题。但是，您可能确实需要避免内存消耗。这给我们带来了下一个想法。

双重迭代

void print_list(node *head)
{
    node* last = NULL;
    while(last != head)
    {
        node* current = head;
        while(current->next != last)
            current = current->next;
        std::cout << current->data << std::endl;
        last = current;
    }
}

这似乎是一个愚蠢的解决方案，因为它具有 O(n^2) 复杂性，但这是计算复杂性。它具有 O(1) 内存复杂度，并且根据实际上下文和确切问题，它可能是您需要的答案。但是这种 O(n^2) 复杂性需要付出很多代价。特别是如果 n 太大，您想避免另一个 O(n) 分配。这使我们想到了最后一个想法。

破解容器

void print_list(node *head)
{
    node* last = NULL;
    for(node* next; head != NULL; head = next)
    {
        next = head->next;
        head->next = last;
        last = head;
    }
    for(node* next; last != NULL; last = next)
    {
        next = last->next;
        last->next = head;
        head = last;
        cout << last->data << endl;
    }
}

您首先修改容器，然后以新顺序迭代。在单链表上，您可以只反转链接，然后在再次反转链接的同时进行反向迭代。它的美妙之处在于它在计算中保持 O(n)，在内存中保持 O(1)。问题是您在执行此操作时使整个容器无效：您的输出操作不会使列表保持不变：这不是异常安全的：如果您的操作在迭代中间失败，则列表不再有效。这可能是也可能不是问题，具体取决于问题。

原文由 lip 发布，翻译遵循 CC BY-SA 3.0 许可协议