Nov 10, 2018

How to find nth element from last in a singly Linked List

In case of singly LinkedList, each node of Linked List contains data and pointer, which is address of next Linked List and last element of Singly Linked List points towards null. Since in order to find middle element of Linked List you need to find length of LinkedList, which is counting elements till end i.e. until you find the last element on Linked List. What makes this data structure question interesting is that you need to find middle element of LinkedList in one pass while you don’t know length of LinkedList.

This is where your logical ability puts into test, whether you are familiar with space and time trade off or not etc. As if you think carefully you can solve this problem by using two pointers. By using two pointers, incrementing one at each iteration and the other at every second iteration. When the first pointer points at end of Linked List, the second pointer will point at middle node of Linked List. In fact this two pointer approach can solve multiple similar problems e.g. How to find 3rd element from last in a Linked List in one Iteration or How to find nth element from last in a Linked List.