Main menu

Media Coverage

<div class="small-4 columns">media 1</div>

<div class="small-4 columns">media 2</div>

<div class="small-4 columns">media 3</div>

Reach to Us

Linked List Traversal in Reverse.

by Pritam on 1 Jul 2015

Write a C/C++ function to print linked list in reverse. Not to be confused with Reversing the linked list. Discuss the complexity.

I will be discussing two approaches. First approach is Iterative and second one is Recursive.

1)Iterative approach using Stack : I will be using a Stack Data structure provided by C++ library. If you don't know that, no need to worry. Being an ADT, all the program will be easy to read. I assume you know basics of Stack (LIFO).

A) Set a pointer to first node of list .  and also take a stack . O(n) space for stack.O(1) time

B) Start from first node, visit each node sequentially and push each node's data into stack,until last node's data is pushed. In this way, first nodes data would be in bottom of stack whereas last nodes data would be on top of stack. O(n) time , n= length of list / no of nodes in list

C) Now start popping the data out of stack and print it.    // O(n) time for n nodes.

I am writing a function here.

// iterative solution using stack
void printReverse_stackIterative(ListNode *head)
{
	stack<int> nodeStack;     // Define a stack of integer. No size is yet mentioned.handled by C++ library
	ListNode *temp = head;    // A temporary pointer ,through which we will visit each node. Good practice to do that,otherwise we will lose track of head in this function
	listEmpty(head);          // this function checks if list is empty and exit program if list is empty.Good practice too.
	while(temp!=NULL){        // Walk until all nodes are visited
		nodeStack.push(temp->data);  // Push nodes data into stack
		temp = temp->next;   // Forward the pointer
	}
       // Until this point each nodes data is pushed onto stack
	while(!nodeStack.empty())   // Until stack is not empty
	{
		cout<<nodeStack.top()<<" "; // Show the top most element
		nodeStack.pop();   // pop out the top most element.
	}
}

Total time  = O (n+n) = O(n), Space =  O(n)  for stack

 

2) Recursive Approach : If you know the basics of Recursion ,Activation record and Function calling, you can relate this approach to above mentioned approach.

// Recusrive Finction print List in reverse order
void printReverse_recursive(ListNode *head)
{
	if (head == NULL)
		return;
	printReverse_recursive(head->next);
	cout<<head->data<<" ";
}

Time =  O(n) , Space = O(1) in the function

0Comment