This article looks at a O(n) algorithm which is time and space efficient.

Algorithms uses two pointers current and behind pointer.

1. The current pointer goes ‘n’ steps from beginning of the list and stops there.

2. the behind pointer is initialised to head/first node.

3. the current pointer is then moved to end of the list, concurrently the behind pointer is moved.

4. when current reaches end the behind pointer will now be pointing to the required node.

This approach is needed because we do not know the tail of linked list (its not a given). it is not as trivial as in case of finding nth node from beginning of a list.

This is just simple math and two pointer usage.if you are still not convinced just work it out on a sheet of paper.

a doubly linked list would be a better DS to solve this problem. In that case we can traverse to end of list and use reverse pointers to come back to the node. But for now i have coded a singly linked list and the above algorithm.

class Node
{
public int item;
public Node next;
public Node(int val)
{
item = val;
}
public void displayNode()
{
System.out.println("[" + item + "] ");
}
}
class LinkedList
{
private Node first;
public LinkedList()
{
first = null;
}
public boolean isEmpty()
{
return (first==null);
}
public void insert(int val)//inserts at beginning of list
{
Node newNode = new Node(val);
newNode.next = first;
first = newNode;
}
public Node delete()//deletes at beginning of list
{
Node temp = first;
first = first.next;
return temp;
}
public void display()
{
System.out.println("List items from head to tail :");
Node current = first;
while(current != null)
{
current.displayNode();
current = current.next;
}
System.out.println("");
}
public Node search(int val)
{
Node current = first;
while(current.item != val)
{
if(current.next == null)
return null;
else
current = current.next;
}
return current;
}
public Node nfromlast(int n)
{
int i;
Node current = first;
for (i=0;i<n;i++)
{
if(current != null)
{
current = current.next;
}
else
{
return null;
}
}
Node behind = first;
while (current != null)
{
current = current.next;
behind = behind.next;
}
return behind;
}
}
class LinkedListBlog
{
public static void main(String[] args)
{
LinkedList object = new LinkedList();
object.insert(10);
object.insert(20);
object.insert(30);
object.insert(40);
object.insert(50);
object.insert(60);
object.display();
Node result = object.nfromlast(5);
System.out.println("the 5th element from the last is: " + result.item);
}
}

OUTPUT:

labuser@ubuntu:~/mfromlastlist$ java LinkedListBlog

List items from head to tail :

[60]

[50]

[40]

[30]

[20]

[10]

the 5th element from the last is: 50

labuser@ubuntu:~/mfromlastlist$

### Like this:

Like Loading...

*Related*

I really like the 2 pointer approach. The post and code is v.clean and good. Thanks for that. But there is a recursive solution to this as well as written here – http://k2code.blogspot.in/2010/04/return-nth-node-from-end-of-linked-list.html:

node* findNthNode (node* head, int find, int& found){

if(!head) {

found = 1;

return 0;

}

node* retval = findNthNode(head->next, find, found);

if(found==find)

retval = head;

found = found + 1;

return retval;

}

Thanks.