Interview Questions
Find n-th last element in single linked list
Given single linked list, find n-th element from the end of the linked list
View Solution
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;
}