Algorithm to Nth-to-Last element in a singly linked list

Algorithm to determine the Nth-to-Last element in a singly linked list of unknown length. If N = 0, then your algorithm must return the last element 
Given that the only way to traverse a singly linked list is forwards from the head, it is not possible to just count N elements from the end of the linked list. Furthermore, the length of the linked list is unknown. We could traverse the list once to determine the number of elements and then traverse the list again to stop at the Nth element from the last element. But this seems a little inefficient. What if we could use 2 pointers?
So what if we use a current pointer and another pointer that is N elements behind the current pointer. When the current pointer reaches the end of the list, the second pointer will be pointing to the element N elements from the end of the list.
Here’s some code to illustrate this logic.
 
Node * findNToLastNode( Node *head, int N )
{
    int i = 0;
    Node *current, *behind;
    current = head;
    for( i = 0; i < N; i++ ) {
        if( current->next ) {
            current = current->next;
        } else {
            return NULL;  // Length of the list is less than N
        }
    }

    behind = head;
    while( current->next ) {
        current = current->next;
        behind = behind->next;
    }

    return behind;
}

No comments:

 
Top Blogs