最近我在一次采访中被问到这个问题。我所能做的就是从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()函数是否具有正确的节点初始化和插入？
有四种可能的方法来实现这一点，每种方法都有自己的优点。
递归
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），在内存中保持0（1）。问题是，在执行此操作时，您会使整个容器无效：您的输出操作不会使列表保持不变：这不是异常安全的：如果您的操作在迭代过程中失败，则列表将不再有效。这可能是问题，也可能不是问题，具体取决于问题。
有一个用while循环反向遍历列表的老技巧。
您在向前的方向上遍历循环，但当您离开每个节点时，您反转链接——即，您获得其当前值（指向下一个节点的指针），但随后将其设置为包含指向上一个节点的指针。当你到达列表的末尾时，你现在有了一个反向的单链列表——也就是说，跟随指针会让你回到列表的开头。
然后你回到开始，边打印边打印每个节点的值，并（再次）反转链接，这样当你完成时，列表就和它开始时一样，链接从开始到结束。
但是，请注意，这可能会导致（例如）多线程代码出现问题。必须将列表从开始到结束以及从开始的整个遍历视为一个单一的原子操作——如果两个线程试图同时遍历列表，就会发生非常糟糕的事情。同样，确保这一例外的安全也可能具有一定的挑战性。
IOW，这些很少是真正问题的有效解决方案（但链表通常也是如此）。然而，它们是向面试官展示你可以玩愚蠢的链表技巧的有效方法。
如果您的列表是[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）我觉得你的main很奇怪。我不明白为什么你的"head"变量是全局的，为什么不在main本身？
最后但同样重要的是，为什么不使用std:：list
在采访中，我被问到一个包含此内容的问题。其目的是同时从两端穿过single list。因此，撤销单一列表不是一种选择。此外，内存空间复杂度应为O(1)。我试图用O(n^2)时间复杂度的嵌套循环来求解。然而，更有效的方法是使用@chuckcottrill和@jerry-coff提到的XOR linked list。通过对节点的前一个和下一个指针应用xor运算，可以将单个列表转换为XOR链表。XOR链表基于XOR运算的以下属性。
a^a^b=b（左侧顺序不重要）
让我们考虑单个列表中的一个节点及其相邻节点：
- X： 上一个节点地址，Y：下一个节点的地址
- 转换为XOR列表时，Y'=X^Y（Y'：Y的新值）
- 在XOR列表上反向遍历时Y^（Y'）=Y^Y^X=X
因此，我们可以获得prev节点（X）并进行反向遍历。以下代码将单个列表转换为XOR链表并进行反向遍历（同时也可以进行正向遍历）：
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;
}
如果我错了，请纠正我。
此解决方案使用迭代方法。一个额外的"上一个"指针用于维护最终将按列表的相反顺序跟随在节点后面的节点。
公共静态节点反向（节点头）｛
Nodes temp;
Nodes previous=null;
while(head!=null)
{
temp=head.next;
head.next=previous;
previous=head;
head=temp;
}
return previous;
}
1）更改
if (traverse->next == NULL)
至
if (traverse == NULL)
2）
while(traverse != NULL) {
// print sth
traverse = traverse->next;
}
3） 我觉得还可以。你为什么要宣布头部在主管道之外？
traverse->next = traverse;
一个你可以使用的可能的解决方案。另一种可能性，
traverse = (traverse->next)- (traverse);
但是您必须错误地检查溢出/下溢。