## Interview Question

Software Engineer Interview Palo Alto, CA

# Print a singly-linked list backwards, in constant space and

linear time.
Tags:
algorithms data-structures

3

One can create a function that takes a node as an argument and checks whether the next of the passed node is NULL or not.In case it is not NULL,the same function is again called for the NEXT node.if the Next of the passed node is NULL,the function prints the value of the node and returns.
void f1(node* p)
{
if(p-&gt;next!= NULL)
{
f1(p-&gt;next)
}
else
{
print (&quot;%d&quot;,p-&gt;value);
}
}

Arpit Agarwal on May 4, 2011
14

Arpit, that's not constant space, that's linear (stack) space, since you will have as many function calls waiting to be returned on the stack as there are nodes.

The trick is to reverse the list first (constant space, linear time when done iteratively or tail-recursively) then print it in order (against constant space, linear time).

Anonymous on May 4, 2011
2

{
if(lln.next != null)
f1(lln.next);
System.out.print(lln.value);
}

Bobby on Jul 6, 2011
3

Bobby, that is not constant space because it uses O(N) stack space.

There are obvoius O(N^2)-time O(1)-space algorithms, and obvious O(N) time O(N) space algorithms.

This is my best guess. Assuming you have exclusive access to the list, you can reverse it, walk it, and then reverse it again. Something like this:

#include
#include

struct node {
int value;
struct node * next;
};

void print_backwards( node * head ) {
node * prev = NULL;
node * next;
while( cur ) {
next = cur-&gt;next;
cur-&gt;next = prev;
prev = cur;
cur = next;
}
cur = prev;
prev = NULL;
while( cur ) {
printf( &quot;%d\n&quot;, cur-&gt;value );
next = cur-&gt;next;
cur-&gt;next = prev;
prev = cur;
cur = next;
}
}

main() {
node a, b, c;
a.value = 1;
a.next = &amp;b;
b.value = 2;
b.next = &amp;c;
c.value = 3;
c.next = NULL;
print_backwards( &amp;a );
}

Kenneth Duda on Jul 27, 2011

This post has been removed.

This post has been removed.

2

{
cout data &quot;;
}

Mohammed on Sep 16, 2011
0

Does this work well? Reverse a list, print it, and then reverse it again.

struct node *reverse(struct node *oldlist) {

struct node *newlist = NULL;
while(oldlist!=NULL) {
struct node *temp = oldlist;
oldlist=oldlist-&gt;next;
temp-&gt;next=newlist;
newlist=temp;
}
return newlist;
}

void display(struct node **q) {
struct node *temp;
temp = *q;
if(*q==NULL) {
printf(&quot;List is empty\n\n&quot;);
}
else {
while(temp!=NULL) {
printf(&quot;%d=&gt;&quot;,temp-&gt;data);
temp=temp-&gt;next;
}
printf(&quot;||\n\n&quot;);
}

}

//p is our list

p = reverse(p);
display(&amp;p);
p = reverse(p);

Unnamed on Jan 18, 2012
0

Thanks to recursion :)

void print_backward(node* n) {
if(n == NULL) return;

print_backward(n-&gt;nxt);

cout val &lt;&lt; endl;
}

Hussein on Apr 5, 2012
0

Yes recursion does the job in linear and constant time. :-)

Balaprasath Rajan on Sep 27, 2012