c++ - 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()功能是否有适当的节点初始化和插入？

score 17 · Accepted Answer

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

递归

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)。问题是您在执行此操作时使整个容器无效：您的输出操作不会使列表保持不变：这不是异常安全的：如果您的操作在迭代中间失败，则列表不再有效。这可能是也可能不是问题，具体取决于问题。

score 4 · Accepted Answer

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

您沿正向走循环，但是当您离开每个节点时，您会反转链接 - 即，您获取其当前值（指向下一个节点的指针），然后将其设置为包含指向前一个节点的指针节点。当您到达列表的末尾时，您现在有一个相反方向的单链表——即，跟随指针将带您回到列表的开头。

因此，然后您回到起点，边走边打印每个节点的值，并（再次）反转链接，这样当您完成后，列表就像它开始时一样，链接从头到尾。

但是请注意，这可能会导致（举一个明显的例子）多线程代码中的问题。从头到尾再回到开头的整个列表遍历必须被视为一个单一的原子操作——如果两个线程试图同时遍历列表，将会发生非常糟糕的事情。同样，使这个异常安全也可能具有一定的挑战性。

IOW，这些很少能有效解决实际问题（但通常链表也是如此）。然而，它们是向面试官展示你可以玩愚蠢的链表技巧的有效方法。

score 1 · Accepted Answer

如果您的列表是 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]：

1）您想输出反转的列表，您的 printList 应如下所示：

int printList(node* traverse)
{
    if (!traverse)
        return (-1);
    printList(traverse->next);
    std::cout << traverse->data << std::endl;
    return (0);
}

2)使用 while 循环实际上是不可能的，除非你做了非常丑陋的事情，比如将每个节点的数据连接到你将打印的结果字符串的开头。

3）你的主要对我来说似乎很奇怪。我不明白为什么你的“头”变量是全局的，为什么不是主要的？

最后但同样重要的是，为什么不使用 std::list？

score 1 · Accepted Answer

我在采访中被问到一个包含这个的问题。它旨在single list同时从两端遍历。因此，扭转单一列表不是一种选择。此外，内存空间复杂度应该是O(1). O(n^2)我尝试使用具有时间复杂度的嵌套循环来解决。但是，更有效的方法是使用XOR linked list@chuckcottrill 和@jerry-coffin 提到的方法。xor通过对节点的 prev 和 next 指针进行操作，可以将单个列表转换为 XOR 链表。XOR 链表基于 XOR 操作的以下属性。

a^a^b = b （左边的顺序不重要）

让我们考虑单个列表中的一个节点及其相邻节点：

X：上一个节点的地址，Y：下一个节点的地址
转换为 XOR 列表时 Y' = X^Y (Y': Y 的新值)
在 XOR 列表上反向遍历时 Y^(Y') =Y^Y^X=X

所以我们可以得到前一个节点（X）并进行反向遍历。以下代码将单链表转换为异或链表并进行反向遍历（同时也可以进行正向遍历）：

    node* curr = head;
    node* prev = NULL;
    node* next= curr->next;

    while (curr) {
        next = curr->next;
        // apply xor to prev and next   
        curr->next = (node*)((uintptr_t)(prev)^(uintptr_t)(next));
        // move pointers forward
        prev = curr;
        curr = next;
    }
    // prev becomes tail node 
    
    // -- Reverse Traversal --
    curr = prev ; // curr points to tail 
    prev = NULL;
    node* temp;
    
    while (curr) {
        cout << curr->data << " ";
        temp = curr;
        // apply xor to prev and next  
        curr = (node*)((uintptr_t)(prev)^(uintptr_t)(curr->next));
        prev = temp;
    }

score 0 · Accepted Answer

如果我错了，请纠正我。

此解决方案使用迭代方法。一个额外的“previous”指针用于维护最终将以列表的相反顺序跟随节点的节点。

公共静态节点反向（节点头）{

    Nodes temp;

    Nodes previous=null;
    while(head!=null)
    {
        temp=head.next;
        head.next=previous;
        previous=head;
        head=temp;
    }
    return previous;

}

score -1 · Accepted Answer

traverse->next = traverse;

您可以使用的可能解决方案。另一种可能，

traverse = (traverse->next)-    (traverse);

但您必须对上溢/下溢进行错误检查。

score -1 · Accepted Answer

1) 改变

if (traverse->next == NULL)

至

if (traverse == NULL)

2)

while(traverse != NULL) {
    // print sth
    traverse = traverse->next;
}

3）对我来说似乎没问题。为什么要在 main 之外声明 head ？

c++ - C ++中的反向遍历单链表

7 回答 7

递归

迭代

双重迭代

破解容器

Related

Reference