## Interview Question

Interview Palo Alto, CA

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

linear time.

## Interview Answer

10 Answers

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).

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

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 <stdio.h> #include <assert.h> struct node { int value; struct node * next; }; void print_backwards( node * head ) { node * prev = NULL; node * cur = head; node * next; while( cur ) { next = cur->next; cur->next = prev; prev = cur; cur = next; } cur = prev; prev = NULL; while( cur ) { printf( "%d\n", cur->value ); next = cur->next; cur->next = prev; prev = cur; cur = next; } assert( prev == head ); } main() { node a, b, c; a.value = 1; a.next = &b; b.value = 2; b.next = &c; c.value = 3; c.next = NULL; print_backwards( &a ); }

Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used.

Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used.

void BWDisplayLinkedList(node* pHead) { if(!pHead) return; BWDisplayLinkedList(pHead->next); cout << pHead->data << " -> "; }

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->next; temp->next=newlist; newlist=temp; } return newlist; } void display(struct node **q) { struct node *temp; temp = *q; if(*q==NULL) { printf("List is empty\n\n"); } else { while(temp!=NULL) { printf("%d=>",temp->data); temp=temp->next; } printf("||\n\n"); } } //p is our list p = reverse(p); display(&p); p = reverse(p);

Thanks to recursion :) void print_backward(node* n) { if(n == NULL) return; print_backward(n->nxt); cout << n->val << endl; }

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

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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->next!= NULL) { f1(p->next) } else { print ("%d",p->value); } }