Interview Questions

Overview

This question requires you to find n-th element counting from the end of the single-linked list. Because the list is single-linked, it is impossible to traverse it backward. The best solution for this problem uses two pointers:

First pointer needs to be first moved (n-1) elements forward in the list - this is relatively easy to do as it requires going to next element in the list in the loop
After this step the second pointer should be set to point to the first element
Having two pointers set to 1-st and n-th position, the algorithm then moves forward those two pointers simultaneously by 1 position in a loop, until the first pointer reaches end of the list.
At this point the second pointer will be pointing to the n-th element from the end of the list

Complexity

Computational complexity of this algorithm is O(n).

Solution

struct Node
{
    int value;
    Node next;
};

Node findNthFromTail(Node *head, int n)
{
    Node *mainPtr = head;
    Node *behindPtr = head;

    //
    // move first main pointer to n-th position
    //

    for (int i = 0; i < n; i++)
    {
        //
        // in case we reach end before
        // this means we do not have enough elements
        //

        if (mainPtr == nullptr)
        {
            return nullptr;
        }

        mainPtr = mainPtr->next;
    }

    //
    // now move both pointers together
    // until main pointer reaches end of list
    //

    behindPtr = head;
    while (mainPtr != nullptr)
    {
        mainPtr = mainPtr->next;
        behindPtr = behindPtr->next;
    }

    //
    // return n-th element from tail
    //
    
    return behindPtr;
}

Find n-th last element in single linked list

Overview

Complexity

Solution