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

Since this sounds like homework, I prefer to help you help yourself instead of giving an actual solution.

I suggest you run this code on some small sample dataset. Use your debugger to run lines step-by-step (you can set a breakpoint at the start of the function). This should give you an idea of how the code works.

You can also Console.WriteLine() to output variables of interest.

Answer 2

This sounds like a homework problem.

In any case, 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).

Answer 3

The key to this algorithm is to set two pointers p1 and p2 apart by n-1 nodes initially so we want p2 to point to the (n-1)th node from the start of the list then we move p2 till it reaches the last node of the list. Once p2 reaches end of the list p1 will be pointing to the nth node from the end of the list.

I've put the explanation inline as comments. Hope it helps:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

Alternatively we can set p1 and p2 apart by n nodes instead of (n-1) and then move p2 till the end of the list instead of moving till the last node:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Answer 4

What do you think regarding this approach.

1. Count length of the linkedlist.
2. Actual Node index from head = linkedlist length - given index;
3. Write a function to travesre from head and get the node at the above index.