CareerCup

package com.career.ds.linkedlist;

public class NthNodeFromEnd {
    public static void main(String args[]) {
        CreateList ll = new CreateList();
        Node head = ll.createList(7, 1);
        ll.displayList(head);
        Node nthNode = ll.getNthNodeFromEnd(head, 2);
        System.out.println();
        System.out.println(2 + " node from end:" + nthNode.getData());
    }

}

class Node {
    public Node(int data) {
        this.data = data;
    }

    int data;
    Node next;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;       
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

class CreateList {

    public Node createList(int length, int data) {
        Node head = new Node((data++));
        Node pointer = head;
        for (int i = 1; i < length; i++) {
            Node temp = new Node((data++));
            pointer.setNext(temp);
            pointer = temp;
        }
        return head;
    }

    public void displayList(Node head) {
        while (head != null) {
            System.out.print(head.getData() + "->");
            head = head.getNext();
        }
    }

    public Node getNthNodeFromEnd(Node head, int nth) {
        Node nthNode = head;
        Node pointer = nthNode;
        int i = 0;
        while (nthNode != null && i != nth) {
            pointer = pointer.getNext();
            i++;
        }

        while (pointer != null) {
            pointer = pointer.getNext();
            nthNode = nthNode.getNext();
        }

        return nthNode;
    }
}

use two pointers:p1 and p2
At first ,p1 point to the Nth node from the head,p2 point to the head.
Then,p1 and p2 move to their next node together,when p1 point to the end,p2 point to the Nth node from the end.

two pointer: the pfirst goes n steps first then with psecond from start together, when the pfirst arrives at the end, the psecond point the nth node form the end.

#include <iostream>

using namespace std;

struct Node
{
int mData;
Node* mNext;

Node(int data , Node* next=nullptr):mData(data),mNext(next) {}
};
struct List
{
List():mHead(nullptr){}

Node* mHead;
void Add(int data)
{
if(!mHead)
mHead = new Node(data);
else
{
Node* temp = mHead;
while(temp->mNext != nullptr)
temp = temp->mNext;
temp->mNext = new Node(data);
}
}
void Display()
{
Node *temp = mHead;
cout<<"\n Content of List are : ";
while(temp != nullptr)
{
cout<<"\t"<<temp->mData;
temp = temp->mNext;
}
}
void Find_Last_nth_Element(int count)
{
if( (count>0) && mHead)
{

Node* temp = mHead;
int index = 0;
while( (index < count) && temp )
{
temp = temp->mNext;
++index;
}
if(index != count)
cout<<"\n lesser elements in List"<<endl;
else
{
Node* nthNode = mHead;
while(temp)
{
temp = temp->mNext;
nthNode = nthNode->mNext;
}
cout<<"\n the "<<count<<" node from last in list is "<<nthNode->mData;
}
}
}
};



void main()
{
cout<<"\n Program Started"<<endl;
List myList;
for(int i=0;i<20;++i)
myList.Add(10*i+i);

myList.Display();
int nthNode=0;
cout<<"\nEnter nth Element from last:";
cin>>nthNode;

myList.Find_Last_nth_Element(nthNode);
cout<<"\n Program Ended"<<endl;
}