反向遍历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)如何printList()用while循环替换递归函数？

3)如果在面试中被问到,该main()功能是否具有正确的节点初始化和插入？

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).问题是你在执行此操作时使整个容器无效:输出操作不会使列表保持不变:这不是异常安全的:如果操作在迭代中间失败,则列表不再有效.根据问题,这可能是也可能不是问题.

Answer 2

使用while循环反向遍历列表有一个老技巧.

你沿着向前的方向走循环,但是当你离开每个节点时,你反转链接 - 即,你获得它的当前值(指向下一个节点的指针),但是然后设置它以便它包含指向前一个节点的指针节点.当你到达列表的末尾时,你现在有一个相反方向的单链表 - 也就是说,按照指针将你带回到列表的开头.

那么你走回到开头,随时打印每个节点的值,并(再次)反转链接,这样当你完成后,列表就像它开始一样,链接从头到尾.

但请注意,这可能会导致(对于一个明显的示例)多线程代码出现问题.从开始到结束并返回到开头的列表的整个遍历必须被视为单个原子操作 - 如果两个线程试图同时遍历列表,则会发生非常糟糕的事情.同样,使这种异常安全也可能具有一定的挑战性.

IOW,这些对于实际问题来说很少是有效的解决方案(但一般情况下链接列表也是如此).然而,它们是向面试官展示你可以玩愚蠢的链表技巧的有效方式.