CareerCup

Node *p = GetFirstNode();
Node *q = p;

for(int i=1;i<=5;i++)
q = GetNextNode(q);

while(q){
p = GetNextNode(p);
q = GetNextNode(q);
}

// So when while loop ends , the p will be the 5th element from the last.

The above solution is fine to use which will keep two pointers separated with the number of positions required from the last. Traverse them together till the "ahead" one reaches to the end.

I just thought to give an alternate solution which will use recursion and count in the reverse order, similarly like if it would have been the nth node from the beginning.

Node GetLastNthNode(Node head, int position) {
static int currentPosition = 0;
// Default value to return.
NODE retNode = NULL;

if(head != NULL) {
   retNode = GetLastNthNode(GetNextNode(head), position);
   if(++currentPosition == position){
      // Update retNode with the required node
      retNode = head;
   } 
}
return retNode;
}

The above solution is fine to use which will keep two pointers separated with the number of positions required from the last. Traverse them together till the "ahead" one reaches to the end.

I just thought to give an alternate solution which will use recursion and count in the reverse order, similarly like if it would have been the nth node from the beginning.

Node GetLastNthNode(Node head, int position) {
static int currentPosition = 0;
// Default value to return.
NODE retNode = NULL;

if(head != NULL) {
retNode = GetLastNthNode(GetNextNode(head), position);
if(++currentPosition == position){
// Update retNode with the required node.
retNode = head;
}
}

return retNode;
}

The above solution is fine to use which will keep two pointers separated with the number of positions required from the last. Traverse them together till the "ahead" one reaches to the end.

I just thought to give an alternate solution which will use recursion and count in the reverse order, similarly like if it would have been the nth node from the beginning.

Node GetLastNthNode(Node head, int position) {
static int currentPosition = 0;
// Default value to return.
NODE retNode = NULL;

if(head != NULL) {
retNode = GetLastNthNode(GetNextNode(head), position);
if(++currentPosition == position){
// Update retNode with the required node.
retNode = head;
}
}

return retNode;
}

Test cases

1. Empty List
2. List with less than "position" elements.
3. Normal scenario with list greater than "position" elements.

Testing this solution

Data structure used: Stack
Step 1 : Push All elements.
Step 1 : Pop "position" elements.
Step 1 : Compare last popped element.

Algo:
- Start with the head node of the linked-list. Continue till the getNextNode(head) is null.
- Keep a Queue (of size 5) that contains the last 5 Nodes.
- return the head of the queue once end is reached.

public Node getLastFifthNode(){
		Node n = getFirstNode();
		if(n == null){
			return null;
		}
		int pos = 5;		
		java.util.Queue<Node> q = new java.util.LinkedList<Node>();
		int qCounter = 0;
		while(n != null){
			//make sure the queue contains maximum 5 elements
			if(++qCounter > pos){
				q.remove(); //remove the head (oldest element)
				qCounter--;
			}
			q.add(n);
			n = getNextNode(n);
		}
		
		if(qCounter == pos){
			//return the first element in the Queue
			return q.remove();
		}else{
			// does not even have 5 elements
			return null;
		}
		
	}

node* returnKthElementFromLast(node* head)
{
if (!head)
return NULL;
node* q = head;
for(int i=0;i<k && q;++i)
{
q = q->next;
}
if (!q and i != k)
return NULL;
node* p = head;
while(q)
{
q = q->next;
p = p->next;
}
return p;
}