向后打印链表 [英] Print linked list backwards
问题描述
在最近一次对嵌入式软件职位的采访中，我被要求
用C语言编写代码，用于打印链表的内容
向后。几分钟后，我想出了递归解决方案。
由于嵌入式软件不满意这个递归，答案
不是面试官所期望的，而是唉是对的。我问
一些朋友他们会如何回答，另一个答案是
反转列表然后在你反向列表时打印内容
第二次。
我正在寻找任何其他可能的解决方案，看起来这些2
是最常见的解决方案。但是，有人提到，如果
是列表不可修改的约束，那么还有另一个
解决方案，但没有提供该解决方案。任何人都可以提供一个
解决方案，除了我提到的2，特别是一个可以工作
而不修改列表？
谢谢，
Josh
" joshc" < jo ******** @ gmail.comwrites：
最近在一次嵌入式软件职位的采访中我被问到了
用于在C中编写代码，用于打印链表的内容
向后。几分钟后，我想出了递归解决方案。
由于嵌入式软件不满意这个递归，答案
不是面试官所期望的，而是唉是对的。我问
一些朋友他们会如何回答，另一个答案是
反转列表然后在你反向列表时打印内容
第二次。
我正在寻找任何其他可能的解决方案，看起来这些2
是最常见的解决方案。但是，有人提到，如果
是列表不可修改的约束，那么还有另一个
解决方案，但没有提供该解决方案。任何人都可以提供一个
解决方案，除了我提到的2，特别是一个可以工作
而无需修改列表？
唯一想到的是建立一个新的，推
项目，因为原始列表是走过。然后您可以打印新的
，或者如果您不再需要它，则在取消分配时打印它
。
当然，这基本上是递归解决方案 - 新列表
扮演调用堆栈的角色 - 所以它也可能在
$ b中不受欢迎$ b嵌入式系统。
BTW，我可以建议编程而不是clc - 你会得到更多的经验吗？你的问题实际上是一个算法一？
-
Ben。 }（（C，yoda）发明）如果
joshc写道：
>
最近在一次关于嵌入式软件职位的采访中我被要求用C编写代码，用于打印链接的
列表的内容向后。几分钟后，我想出了递归的
解决方案。由于嵌入式
软件不满意这种递归，答案并不是面试官所期望的，但
唉，这是正确的。我问了一些朋友他们会怎么回答
，另一个答案就是反转清单，然后打印
内容，当你再次反转清单时。
我正在寻找任何其他可能的解决方案，似乎这两个是最常见的解决方案。但是，有人提到
，如果存在列表不可修改的约束，那么
是另一种解决方案，但没有提供该解决方案。任何人都可以提供除了我提到的2之外的解决方案，尤其是那些在不修改列表的情况下可以工作的
吗？
这可能会耗费大量的堆栈空间（在堆栈系统上）以获得
长列表，但它应该可以工作（未经测试）
#include< stdio.h>
struct node {
struct node * next;
char * data;
};
void revprint（struct node * root）{
if（root-> next）revprint（root-> next）;
puts（root-> data）;
}
int main（无效）{
struct node * root;
root = makelist（无论如何）; / *代码品尝* /
revprint（root）;
返回0;
}
-
Chuck F（cinefalconer at maineline dot net）
可用于咨询/临时嵌入式和系统。
< http://cbfalconer.home.att.net>
" joshc" < jo ******** @ gmail.com写信息
新闻：11 ********************** @ n67g2000cwd.googlegr oups.com ...
最近我在一次嵌入式软件职位的采访中被要求
来编写代码，在C中，用于打印链表的内容
向后。几分钟后，我想出了递归解决方案。
由于嵌入式软件不满意这个递归，答案
不是面试官所期望的，而是唉是对的。我问
一些朋友他们会如何回答，另一个答案是
反转列表然后在你反向列表时打印内容
第二次。
我正在寻找任何其他可能的解决方案，看起来这些2
是最常见的解决方案。但是，有人提到，如果
是列表不可修改的约束，那么还有另一个
解决方案，但没有提供该解决方案。任何人都可以提供一个
解决方案，除了我提到的2，特别是一个可以工作
而不修改列表？
谢谢，
Josh
我相信面试官不喜欢你的解决方案的唯一原因是因为
你在时间和空间复杂性方面都遇到了问题O（n）。因此，
给出的最佳解决方案是你的朋友。它在时间上仍然是O（n），但它在空间复杂性上是$（b）。
基本上，还有另一种解决问题的方法如果你不能修改
列表，那就是建立新列表。但是，如果你在迭代给定的列表时构建新列表
，那么是否接受这样的解决方案
是值得怀疑的，因为它也会耗尽内存 - 不是在堆栈上，而是在堆上。
所以，虽然它没有按照列表的长度按比例填充堆栈，但是它填满了堆栈 -
这两个都是内存消耗。
更少的内存消耗解决方案，但仍然与
列表的长度成正比，如果你只保存内存地址通过列表迭代
时的结构，而不是构建第二个列表。你需要一个新的
结构，因为你不知道第一个列表有多少元素，但
它可能要小得多（每个结构只有8个字节） ，因为你需要
a指向你需要打印出的结构元素，第二个指向这个新列表中前一个元素的
指针。你可以
也可以创建一个大小为80字节的数组，每次填写它时，你会对它进行一次重新分配，并使其大80字节。但是，如果原始列表很大，这可能会显着降低程序的速度。
-
" It世界很容易生活在世界的意见之后;孤独轻松
住在我们自己之后;但伟大的人就是在人群中间的人。
保持完美的甜蜜独处的孤独。
Ralph Waldo Emerson，自力更生1841年/> http://pinpoint.wordpress.com/
In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.
I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn''t provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?
Thanks,
Josh
"joshc" <jo********@gmail.comwrites:
In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.
I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn''t provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?The only thing that springs to mind is to build a new one, "pushing"
items onto it as the original list is traversed. You can then print
the new one, or print it as you de-allocate it if you won''t need it
again.
Of course, this is essentially the recursive solution -- the new list
playing the role of the call stack -- so it may also be frowned on in
embedded systems.
BTW, may I suggest comp.programming rather than c.l.c -- you will get
wider experience there and your question is really an algorithm one?
--
Ben. } ((C, "yoda")invented) if
joshc wrote:>
In an interview for an embedded software position recently I was
asked to write code, in C, for printing the contents of a linked
list backwards. After a few minutes I came up with the recursive
solution. Being that recursion is frowned upon in embedded
software, the answer was not what the interviewer expected, but
alas it was correct. I asked some friends how they would have
answered and another answer is to reverse the list and then print
the contents as you reverse the list a second time.
I was searching for any other possible solutions and it seems
these 2 are the most common solutions. However, someone mentioned
that if there is a constraint that the list is unmodifiable, there
is another solution but didn''t provide that solution. Can anyone
provide a solution besides the 2 I mentioned, especially one that
would work without modifying the list?This might eat up a lot of stack space (on stack systems) for a
long list, but it should work (untested)
#include <stdio.h>
struct node {
struct node *next;
char *data;
};
void revprint(struct node *root) {
if (root->next) revprint(root->next);
puts(root->data);
}
int main(void) {
struct node *root;
root = makelist(whatever); /* code to taste */
revprint(root);
return 0;
}
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
"joshc" <jo********@gmail.comwrote in message
news:11**********************@n67g2000cwd.googlegr oups.com...In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.
I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn''t provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?
Thanks,
Josh
I believe the only reason the interviewer did not like your solution is because
you have made the problem O(n) in both temporal and spatial complexity. Thus,
the best solution given was by your friends. It remains O(n) in temporal, but it
is O(1) in spatial complexity.
Basically, there IS another way to solve the problem if you must not modify the
list, and that is by building the new list. However, if you build the new list
as you iterate through the given one, it is questionable if such a solution
would be accepted, because it also uses up memory - not on stack, but on heap.
So, while it doesn''t fill the stack up in proportion to the length of the list,
it fills the heap - and both are memory consuming.
Less memory-consuming solution, but still proportional to the length of the
list, is if you only save memory addresses of the structures while iterating
through the list, rather than building a second list. You would need a new
structure for that, as you do not know how many elements the first list has, but
it could be considerably smaller (only 8 bytes per structure, for you would need
a pointer to the structure elements you need to print out, and the second
pointer which would point to the previous element in this new list). You could
also make an array sized say 80 bytes, and each time you fill it out, you do a
realloc on it and make it 80 bytes larger. This could, however, significantly
slow down the program if the original list is large.
--
"It is easy in the world to live after the world''s oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/
这篇关于向后打印链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
