Posts Tagged ‘Nth element from the last element’

Consider a singly linked list. What is the optimal way to traverse to an Nth element from the last element of that singly linked list. Any algorithms or logic to achieve in optimal way?

Naive soln :

  • First find the total number of nodes, by iterating the entire list ..
  • Now subtract the nth last node from the total number
  • Now again iterate from the head node to the nth nodeā€¦

But it require two complete iteration..

Optimized soln :

  • Create two pointers and point those pointers to head node..
  • Iterate first pointer to nth node..
  • Now, iterate both first node pointer and second node pointer, until first node pointer reaches the end of the list .. Now second pointer will be pointing to the nth node from the last node.. (more…)

Read Full Post »