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

Question

Anónimo · Accepted Answer

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

Kenneth Duda · Answer

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 * cur = head;
   node * next;
   while( cur ) {
      next = cur->next;
      cur->next = prev;
      prev = cur;
      cur = next;
   }
   cur = prev;
   prev = NULL;
   while( cur ) {
      printf( "%d
", 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 );
}

Arpit Agarwal · Answer

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

Mohammed · Answer

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

Bobby · Answer

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

Unnamed · Answer

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

");
		}
		else {	
			while(temp!=NULL) {	
				printf("%d=>",temp->data);
				temp=temp->next;
			}
			printf("||

");
		}

	}

//p is our list

p = reverse(p);
display(&p);
p = reverse(p);

Hussein · Answer

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

Balaprasath Rajan · Answer

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

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo