Solution: Return the Nth Node from End

Statement

Given the head of a linked list, return the $n^{th}$ node from the end of the linked list.

Constraints:

• The number of nodes in the list is $k$.

• $1 \leq$ $k$ $\leq 10^3$

• $-10^3\le$ Node.value $\leq 10^3$

• $1\le$n $\le$

Solution 1: Double iteration

In this solution, we first determine the length of the linked list, and based on this length, we find the position of the $n^{th}$ element from the end of the linked list. Then, traverse the list to find the node at that position and return its value.

The steps of the algorithm are given below:

1. We calculate the length of the linked list. For this, we iterate through the list, starting from the head, and increment a counter for each node encountered until reaching the end of the list.

2. We initialize a variable, position, with$\text{(length of the linked list - n + 1)}$, which gives the position of the $n^{th}$ element from the end of the linked list.

3. Next, we start traversing from the head of the linked list position times.

4. After traversing the linked list position times, we return the data of the current node in the traversal. This node is the $n^{th}$node from the end to be returned from the linked list.

Let’s look at the code for this solution below: