Finding the nth node from the end in a linked list

Given a linked list, how do efficiently find the nth node from the end?

For example in the following linked list, 3rd node from the end is ‘6’.

2 -> 1 -> 6 -> 5 -> 9

One obvious method is to find the length of the linked list (len) by going through the list. calculate the difference (len – n). Again traverse the list (len – n) times to get the required node. Though this approach is O(n), we traverse the list twice.

We can do it in just one iteration itself. We take two pointers one main pointer (ptr) and one helper pointer (hPtr). First we travel a distance of n nodes with hPtr. Then we start from the beginning with main pointer also. By the time the hPtr reaches the end, ptr would be pointing to the nth node from the end.

Here is Object Oriented implementation of this in C++

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

view raw NthNodeFromEnd.cpp hosted with

by GitHub

Leave a Reply Cancel reply