Print linked list backwards

K

Keith Thompson

Sourcerer said:
Yes, that is my default assumption, because this is the most common in
my experience. I'm not trying to be infinitely accurate.

There's no need to be "infinitely accurate". Just acknowledge the
assumption. For example, something like "This requires 8 bytes per
node (assuming 4-byte pointers)" is perfectly fine.

[...]
True, you save memory and it can be faster than realloc(), but still
memory consumption remains proportional to the length of the list. But
these are the only options - either modify the list, or consume
memory. So, which will it be is purely an engineering decision - weigh
the alternatives and choose the best one.

As it turns out, those aren't the only options. Chris Torek posted a
solution that neither modifies the list nor allocates O(n) memory --
but it requires O(n**2) time. (I think you could speed up Chris's
method by a constant factor by allocating a fixed-size array of
pointers, reversing the list in chunks rather than one element at a
time.)
 
S

Sourcerer

Keith Thompson said:
As it turns out, those aren't the only options. Chris Torek posted a
solution that neither modifies the list nor allocates O(n) memory --
but it requires O(n**2) time. (I think you could speed up Chris's
method by a constant factor by allocating a fixed-size array of
pointers, reversing the list in chunks rather than one element at a
time.)

Yes, sorry. I forgot about it.

--
"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/
 
R

Richard Harter

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?

A third solution, which no one seems to have mentioned, is to partition
the list. You can use the double pointer technique to find the midpoint
of the list. Process the last half recursively, then the first half.
The time cost is O(n*log n) and the space cost is O(log n). This gives
us three classes of solution:

Walk to last then to next last etc: time O(n*n), space O(1)
Partition the list: time O(n*log n), space O(log n)
Reverse copy the list: time O(n), space O(n)

Which to choose depends on circumstances.

Considered as an interview question, a "good" answer is to give all
three solutions, and explain the tradeoffs. Just answering with
whatever occurs to you first is not quite as good. Part of good
software design is knowing what your options are.

Followups set to comp.programming.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Reversing a linked list 116
linked list 14
Linked list need help... 13
Linked list allocation 8
Odd linked list runtime error 6
reading the source of calling a singly-linked list 4
Linked list in C 4
Doubly linked list 6

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top