Nth element from the end of a linked list

Let us consider a linked list with five nodes:

For n = 2, the second element from the tail, which is 98, has to be returned.

Given a linked list, whose size is unknown, the element which is at the n^th position from the end of the linked list has to be found.

A straight-forward approach is to traverse the linked list once to calculate its size k. Perform a second traversal of (k-n+1) steps to point to the n^th node from the end of the list. This method requires two traversals.

A better approach is to perform only one traversal. Use two pointers – say, prev and cur. To initialize the pointers, position the prev pointer to the head node and advance the cur pointer so that it points to the n^th node from the head.

From this point onwards, advance both the pointers by one step at a time until the cur reaches the end of the list. At this point, the prev pointer will be pointing to the n^th node from the end of the list. The complexity is still O(n) but requires only one traversal.

Consider the following node structure:

struct Node {

  int data;

  Node* next;

};

Here is the C++ code:

void NthToLastElement(int n, Node* head) {

  Node* prev = head;

  Node* cur = head;

  int i = 0;

  while(i < n && cur != NULL) { //advance the cur pointer by n steps

    cur = cur->next;

    ++i;

  }

  if(cur == NULL) { //n > k

    cout << "Not enough elements";

    exit(0);

  }

  while(cur != NULL) {

    cur = cur->next;

    prev = prev->next;

  }

  cout << "Nth element from the end: " << prev->data << endl;

}