Efficient method for Finding Nth element from the end of a Linked List

[wpdm_package id=’1343′]

[wpdm_package id=’1345′]

Algorithm:

  • Use 2 pointers ptr and newptr.
  • Initially both points to head node of the list.
  • Move ptr ‘n’ times.
  • After this, start moving both ptr and newptr till ptr reaches end of the list.
  • As a result, newptr will now be pointing to the nth node from the end of the linked list.

This is comparatively more efficient approach as we do not need to create a hash table, also, we just do a single scan through the linkedlist.

Time Complexity: O(n), Space Complexity: O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *