Find nth node from the end of a Linked List.

Question:

Suppose you are given a Linked List as 45-> 123-> 87-> 11-> 53-> 24-> 412-> 22. And we have to find the n^th node from the end.

Input:- n = 3
Output:- 24

BRUTE FORCE APPROACH:-

In this method, start with the first node and count how many nodes are there after that node. If the number of nodes are < n-1, then return saying, “fewer number of nodes in the list.” If the number of nodes are > n-1 then go to the next node. Continue this until the number of nodes after the current node are n-1.

Time Complexity:- O(n²), for scanning the remaining list (from the current node) for each node.
Space Complexity:- O(1)

IMPROVING THE COMPLEXITY:-

The complexity of the above problem can be improved by using a hash table. Consider the list:- 5-> 1-> 17-> 4-> NULL.

In this approach, create a hash table whose entries are <position of node, node address>. That means, key is the position of the node in the list and the value is the address of that node.

By the time we traverse the complete list(for creating hash table), we an find the list length. Let us say, the list length is M. To find the nth term from the end of the Linked List, we can convert this to M-n+1^th from beginning. Since we already know the length of the list, its just a matter of returning M-n+1^th key value from the hash table.

Time Complexity:- Time for creating hash table. Therefore T(M) = O(M).
Space Complexity:- O(M), because we are creating a hash table of size M.

AN APPROACH WITHOUT USING THE HASH TABLE

In the above solution, what actually we are doing is finding the size of the Linked List. That means, we are using hash table to find the size of the Linked list. We can find the length of the linked list just after starting at the head node and traversing the list. So, we can find the length of the list without creating the hash table. After finding the length compute M-n+1 and with one more scan we can get M-n+1^th term from the beginning.

Time Complexity:- Time for finding length + Time for finding M-n+1th node from beginning, Therefore T(n) = O(n) + O(n) ≈ O(n).
Space Complexity:- O(1), since no hash table is created.

SOLVING THE PROBLEM IN ONE SCAN (MOST EFFICIENT)

Use 2 pointers:-

• pNthNode
• pTemp

Both the nodes point to the HEAD of the list. pNthNode starts moving only after pTemp has moved n nodes forward. From there, both nodes move forward until pTemp reaches NULL.
pNthNode now points at the n^th node from the end.

/*
Defining a function to find the nth node from the end.
*/
struct node * nthNodeFromEnd(struct node * head, int n)
{
	// we need to find the nth node from the end.
	struct node * pTemp = head;
	struct node * pNthNode = head;

	int nCurrentElement = 0;

	int counter = 0;

	while(counter != n)
	{
		pTemp = pTemp -> next;
		counter++;
	}

	while(pTemp != NULL)
	{
		pNthNode = pNthNode -> next;
		pTemp = pTemp -> next;
	}

	return pNthNode;
}

Time Complexity:- O(n)
Space Complexity:- O(1)

A working demo can be downloaded here. You can open it in any of the text editor like notepad, gedit etc…