This program prints the nth node from the end of a linked list.

NthNodeFromEnd.cpp

#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
	private:
		//data member
		int data;
		//pointer to next node in the linked list
		SLLNode *nextPtr;
	
	public:
		
		//Single argument constructor
		//initializes data with d, next pointer to NULL
		SLLNode(int d):data(d),nextPtr(NULL)
		{
		}
		//to initialize both members
		SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
		{			
		}
		//returns the data
		int getData()
		{
			return data;
		}
		//sets the data
		void setData(int d)
		{
			this->data = d;
		}
		//gets the next pointer
		SLLNode* getNext()
		{
			return this->nextPtr;
		}
		//sets the next pointer
		void setNext(SLLNode *ptr)
		{
			this->nextPtr = ptr;
		}
};

//defines the actual single linked list
class SinglyLinkedList
{
	private:
		//maintain two pointers to the start and the end
		//so that we can append at the end easily (constant time complexity)
		SLLNode * head;
		SLLNode * tail;
	public:
		SinglyLinkedList()
		{
			head = NULL;
			tail = NULL;
		}
		//adds the node to the end of the list
		void appendNode(SLLNode* ptr)
		{
			//check if list is empty
			if( head == NULL)
			{
				//update both the pointers
				head = tail = ptr;
			}
			else //simply append at the end, and move the tail pointer
			{
				tail->setNext(ptr);
				tail = tail->getNext();
			}
		}
		//gets the length of the list
		int getLength()
		{
			int length = 0;
			
			SLLNode* ptr = head;
			
			while ( ptr != NULL )
			{
				length++;
				ptr = ptr->getNext();
			}
			return length;
		}
		
		//get Nth node from the end
		SLLNode* getNthNodeFromLast(int n)
		{
			SLLNode * ptr = head; //result pointer
			SLLNode * hPtr = head; //helper pointer
			
			int i = n;
			
			//travel n distance using helper pointer
			while ( i > 0 && NULL != hPtr)
			{
				hPtr = hPtr->getNext(); 
				i--;
			}
			//handle the case where n > length of the list; return NULL
			if( i > 0)
				return NULL;
				
			while( hPtr != NULL )
			{
				hPtr = hPtr->getNext();
				ptr = ptr->getNext();
			}
			return ptr;
		}
};

int main()
{
	SinglyLinkedList list;
	list.appendNode(new SLLNode(1));
	list.appendNode(new SLLNode(2));
	list.appendNode(new SLLNode(3));
	list.appendNode(new SLLNode(4));
	list.appendNode(new SLLNode(5));
	list.appendNode(new SLLNode(6));
	
	//The answer should be 4
	SLLNode * ptr = list.getNthNodeFromLast(3);
	
	if( ptr )
		cout << "3rd node from the end is " << ptr->getData()<<endl;
	else
		cout << "Invalid index!" <<endl;
		
	// 0 is not a valid index; let's see if our program handles this	
	ptr = list.getNthNodeFromLast(0);
	if( ptr )	
		cout << "0th node from the end is " << ptr->getData() << endl;
	else
		cout << "Invalid index!" << endl;
		
	// 7 is also not a valid index as it is greater than list length
	ptr = list.getNthNodeFromLast(7);
	if( ptr )	
		cout << "0th node from the end is " << ptr->getData() << endl;
	else
		cout << "Invalid index!" <<endl;
		
	return 0;
}