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

Posted by Codenotguru on Stack Overflow See other posts from Stack Overflow or by Codenotguru
Published on 2010-04-08T08:03:56Z Indexed on 2010/04/09 5:13 UTC
Read the original article Hit count: 291

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;
 }

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about datastructures