Finding nth last element in a singly link list

Problem: Given a singly link list and not knowing its length in advance find the nth last element

This problem though is pretty trivial but reveals some interesting facts about a link list. Since there is no concept of indexing so we have no way of knowing before hand when to stop iterating in a list. Once you have reached the end of list, there is no way of coming backwards unless you start again from the beginning.

The simplest solution that comes to mind is, first iterate through the whole list once, counting the number of nodes. Once you are through and know the size, then do the second iteration counting nodes and stopping when total – n = required node is found.

Although the above solution is workable and takes only about 2n iterations which is O(n). However, there is a general and more elegant strategy which should be established as one of the rules of searching in a linked list.

The idea is that you should have two pointers iterating. The gap between the first and the second should be exactly n. So when the first reaches the end or null, the second pointer is pointing towards exactly the node we require.

The concept of having multiple pointers iterating at different speeds / gap between them is very fundamental and is used to solve many important problems in link lists.

I have pasted all of my functions i.e. insertion at list head, printing list along with the finding nth element function to make the whole program directly usable for even a beginning programmer who hasn't coded link lists before and has a basic understanding.


#include <iostream>

using namespace std;


struct Node  // A c++ struct is automatically used as a type.

{

    int data;

    Node *next;

};


Node * head; // The head of list


void insertAtHead(int val)

{

    Node * newNode = new Node;

    newNode->data = val;

    newNode->next = NULL;


    if(head != NULL)

    {

        newNode->next = head;

        head = newNode;

    }


    else

        head = newNode;


}


void printList(Node *cHead)

{

    Node * temp = cHead;


    while(temp != NULL)

    {

        cout << " " << temp->data << " ";

        temp = temp->next;

    }


    cout << endl;

}


// For simplicity i have ommitted checks if the list is null or contains at least n

// elements. These must be there if this code is used in any real application

Node * findNthLastElement(Node *Lhead, int n)

{

    Node *first, *second;


    first = Lhead;


    // Take first n nodes ahead

    for(int c=0; c < n; c++)

        first = first->next;


    // Initialize second from beginning

    second = Lhead;


    // Move both first and second ahead one node at a time until first reaches null

    while(first != NULL)

    {

        first = first->next;

        second = second->next;

    }


    return second;

}


int main()

{

    for( int i=12; i>0; i--)

    {

        insertAtHead(i);

    }


    printList(head);


    // Test code to check for nth last element varying from 1-10

    for(int n=1; n<=10; n++)

    {

        cout << n << "th last element is " <<(findNthLastElement(head, n))->data << endl;

    }


    return 0;

}