Interview Question

Software Engineer Interview Palo Alto, CA

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

  linear time.
Tags:
Answer

Interview Answer

10 Answers

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

Arpit Agarwal on May 4, 2011
10

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
1

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

Bobby on Jul 6, 2011
1

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 );
}

Kenneth Duda on Jul 27, 2011
7

Reverse the list, print, then reverse it back.

3 O(n) operations = O(n). O(1) space used.

Simple on Aug 14, 2011
2

Reverse the list, print, then reverse it back.

3 O(n) operations = O(n). O(1) space used.

Simple on Aug 14, 2011
2

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

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

Unnamed on Jan 18, 2012
0

Thanks to recursion :)

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

    print_backward(n->nxt);

    cout << n->val << endl;
}

Hussein on Apr 5, 2012
0

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

Balaprasath Rajan on Sep 27, 2012

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up