How to find nth element from the end of a singly linked list?

Question

The following function is trying to find the nth to last element of a singly linked list.

For example:

If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7.

Can anybody help me on how this code is working or is there a better and simpler approach?

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
    if (p2 == null) {
      return null; // not found since list size < n
    }
    p2 = p2.next;
  }

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}

Answer 1

Your algorithm works by first creating references to two nodes in your linked list that are N nodes apart. Thus, in your example, if N is 7, then it will set p1 to 8 and p2 to 4.

It will then advance each node reference to the next node in the list until p2 reaches the last element in the list. Again, in your example, this will be when p1 is 5 and p2 is 10. At this point, p1 is referring to the Nth to the last element in the list (by the property that they are N nodes apart).