Solution: Return the Nth Node from End

Let’s solve the Return the Nth Node from End problem.

Statement

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

Constraints:

  • The number of nodes in the list is kk.

  • 11 \leq kk 103 \leq 10^3

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

  • 11\len \lekk

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 nthn^{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(length of the linked list - n + 1)\text{(length of the linked list - n + 1)}, which gives the position of the nthn^{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 nthn^{th}node from the end to be returned from the linked list.

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.