ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to find the nth node from last/tail of a Linked List

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$

One response to “Algorithm to find the nth node from last/tail of a Linked List

  1. Kinshuk May 2, 2014 at 5:35 pm

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: